수학과의 개발자 도전기

-문제:https://www.acmicpc.net/problem/16946

처음에는 dfs로 풀려고 했는데, 잘 풀리지 않아서 bfs로 풀어보았다. 

그런데 함수의 값을 반환해서 어떻게 해보려고 했는데 그게 잘 되지 않아 구글링을 했다.

찾아보니 bfs가 끝났을 때 s 행렬을 바꿔주는 방식으로 진행하면 따로 반환없이 바로 출력하면 된다 

찾아보니 이 블로그가 설명이 더 깔끔한 것 같다. 이거를 기준으로 다시 공부 해봐야할 것 같다

참고한 블로그

-정답풀이:

from collections import deque

def bfs(cur_r,cur_c,itr):
    q=deque()
    q.append([cur_r,cur_c])
    v[cur_r][cur_c]=itr
    cnt=1
    tmp=[]
    while q:
        x, y=q.popleft()
        for dx, dy in dr:
            nx, ny=x+dx, y+dy
            if 0<=nx<n and 0<=ny<m and v[nx][ny]!=itr:
                if not a[nx][ny]:
                    q.append([nx, ny])
                    v[nx][ny]=itr
                    cnt+=1
                else:
                    tmp.append([nx, ny])
                    v[nx][ny]=itr
    for i, j in tmp:
        c[i][j] += cnt
        
n,m=map(int,input().split())
a=[list(map(int,input())) for _ in range(n)]
v=[[0]*m for _ in range(n)]
c=[[0]*m for _ in range(n)]
dr=[[-1,0],[1,0],[0,-1],[0,1]]
itr=1
for i in range(n):
    for j in range(m):
        if a[i][j]:
            c[i][j]=1
for i in range(n):
    for j in range(m):
        if not a[i][j] and not v[i][j]:
            bfs(i,j,itr)
            itr+=1
for i in range(n):
    for j in range(m):
        print(c[i][j] % 10, end='')
    print()

-틀린풀이:

나름 작성해본 코드인데 함수에서 반환하는 것을 잘 못해서 TypeError가 발생했다 

함수에 대해 공부해야할 것 같다,,,

from collections import deque
n,m=map(int,input().split())
s=[list(map(int,list(input()))) for _ in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
ones=[]
for i in range(n):
    for j in range(m):
        if s[i][j]==1:
            ones.append([i,j])
def bfs(x,y):
    q=deque()
    q.append((x,y))
    cnt=1
    while q:
        x,y=q.popleft()       
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx <n and 0<=ny<m:
                if not s[nx][ny]:
                    cnt+=1
                    q.append((nx,ny))
                else:
                    continue 
    return cnt
for i in range(len(ones)):
    for x,y in ones[i]:
        ans=bfs(x,y)
        s[x][y]=ans%10
for i in range(n):
    print(s[i])

오류 발생한 부분

2022.08.09

IDE에서 오류나는 걸로 다음과 같이 코드 작성했더니 정상작동했다 

이때는 아직 코드작성이 더 미숙해서 겪었던 문제였던 것 같다 

for x,y in ones :
    ans = bfs(x,y)
    s[x][y] = ans % 10

-문제:https://www.acmicpc.net/problem/1941

꽤 쉬운 문제라고 생각했는데 찾아보니 그리 쉽지 않은 문제라서 추가로 공부를 해야할 것 같다

참고한 블로그 

전형적인 백트래킹 문제이고, 조합으로 접근하는 문제다

dfs함수로 25개의 칸에서 7개의 칸을 선택하는 조합을 구현한다 

0부터 24까지의 숫자를 5*5행렬의 좌표로 변환해주며 탐색한다( 23번은 4행 3열에 위치해있다)

해당 위치가 'Y'이면 ycnt+1하며 재귀로 넘겨주고, 'S'라면 그냥 인자를 그대로 넘긴다 

depth도 사용하지 않고, ycnt도 사용하지 않고 인덱스만 넘기는 경우가 있어서(이런 경우가 어떻게 있지?) dfs(depth,ycnt,idx+1)을 추가한다

백트래킹으로 Y를 4번 이상 만났다면 return하여 가지치기를 함으로써 어느정도 거를 수 있다. 밑에서 ycnt>=4인 경우다.

(가지치기가 무엇?) 위 상황말고도 탐색할 숫자가 나의 남은 선택 수보다 작으면 가지치기를 해준다

check함수를 통해 7개의 자표들이 서로 연결된 좌표인지 확인한다

0-24까지의 숫자를 5*5행렬 위치로 변환하고, 4방향 탐색을 통해 갈 수 있는 곳의 숫자가 현재 조합 숫자에 포함된 숫자라면 

재귀를 돌린다 

매 조합의 경우마다 visit와 available 변수를 초기화해줘야 한다

available==7인 경우는 7개의 위치 좌표가 서로 연결된 것이므로 result+=1을 해준다 

-정답풀이: 

nextNum+= nr*5+nc로 써서 계속 UnboundLocalError 발생해서 고생했다,,

from sys import stdin
input=stdin.readline
dr=[-1,1,0,0]
dc=[0,0,-1,1]

def check(num):
    global available 
    r=num//5
    c=num%5
    for i in range(4):
        nr,nc=r+dr[i],c+dc[i]
        if 0<=nr<5 and 0<=nc<5 and not visit[nr][nc]:
            nextNum=nr*5+nc
            if nextNum in p:
                visit[nr][nc]=1
                available+=1
                check(nextNum)
                
#깊이, Y의 갯수, 사용할 숫자 인덱스                 
def dfs(depth,ycnt,idx):
    global result,available,visit
    if ycnt>3 or 25-idx <7-depth: #가지치기 
        return 
    if depth==7:
        available=1
        visit=[[0]*5 for _ in range(5)]
        sr,sc=p[0]//5,p[0]%5
        visit[sr][sc]=1
        check(p[0])
        if available ==7:
            result+=1
        return 
    r=idx//5
    c=idx%5
    
    if A[r][c]=='Y':
        p.append(idx)
        dfs(depth+1,ycnt+1,idx+1)
        p.pop()
    else:
        p.append(idx)
        dfs(depth+1,ycnt,idx+1)
        p.pop()
    dfs(depth,ycnt,idx+1)
    
A=[input().rstrip() for _ in range(5)]
visit=[[0]*5 for _ in range(5)]
result=0
p=[]
dfs(0,0,0)
print(result )

-문제: https://www.acmicpc.net/problem/1405

-정답풀이:

direction=[(-1,0),(1,0),(0,-1),(0,1)]으로 방향 이동하는 리스트 구현하기 

visit.pop() 구현하기 

n번만큼 주어진 확률*100이 곱해졌을 것이므로 (0.01**n)을 ans에 곱해서 출력해주기 

def dfs(x,y,cnt,visit):
    global ans   
    if len(visit)==n+1:
        ans+=cnt
        return ans
        
    for i in range(4):
        nx,ny=x+direction[i][0],y+direction[i][1]
        if (nx,ny) not in visit:
            visit.append((nx,ny))
            dfs(nx,ny,cnt*probability[i],visit)
            visit.pop()
            
n,E,W,S,N=(map(int,input().split()))
probability=[E,W,S,N]
direction=[(-1,0),(1,0),(0,-1),(0,1)]

ans=0
dfs(0,0,1,[(0,0)])

print(ans*((0.01)**n))

-처음 풀이: 

고쳐야할 점이 많은 코드이다

1. 먼저 방문한 위치를 어떻게 표현해야할지 몰랐다(문제에서 로봇은 행렬위에서 움직이는 게 아니라는 생각에 어떻게 표현해야하는지 몰랐는데, 그냥 이동하는 좌표를 하나씩 visit에 추가해주면 된다는 것을 알았다)

2. 하나의 깊이로 이동하기 때문에 중간에 ans+=cnt 코드가 있으면 cnt의 값이 계속해서 축적돼서 정확한 ans 값이 나오지 않는다 

그래서 dfs함수를 나올때 ans +=cnt를 해줘야한다 

3. probability[i] !=0 은 굳이 필요없는 코드이다 

4. 처음 숫자 input()할 때, n,e,w,s,n에서 n이 중복되므로 둘 중에 하나를 다른 문자로 변경했어야했다. 이거 발견 못해서 몇번이나 시간초과가 발생했다 

def dfs(x,y,cnt,n):
    #방문처리(위치를 어떻게 표현해야할지 몰랐다)
    global ans
    ans+=cnt
    if n==0: 
    	return ans
        
    for i in range(4):
        if probabilty[i]!=0 and not visit:
            if direction[i]=='E':
                dfs(x+1,y,cnt*probability[i],n-1)
            if direction[i]=='W':
                dfs(x-1,y,cnt*probability[i],n-1)
            if direction[i]=='S':
                dfs(x,y+1,cnt*probability[i],n-1)
            if direction[i]=='N':
                dfs(x,y-1,cnt*probability[i],n-1)
            
n,e,w,s,n=(map(int,input().split()))/100
n=n*100
probability=[e,w,s,n]
direction=['E','W','S','N']
ans=0
dfs(0,0,1,n)
print(ans)

-문제: https://www.acmicpc.net/problem/2250

이진트리의 순회 방법을 처음 접해서 어떻게 풀어야할지 몰랐던 문제다

문제의 접근법은 중위순회이다. 

중위순회를 하면서 각 레벨에 따라 거리를 저장하는 것이 중요하다 

중위 순회란?

: 왼쪽 하위 트리부터 오른쪽 하위 트리 방향으로 방문하는 순회. 노드->부모노드->형제노드 순서로 진행하고,

예시로는 수식트리가 있다 

(1) 왼쪽 하위 트리부터 시작 : 가장 왼쪽의 '잎 노드'부터 시작한다는 말

(2) 루트

(3) 오른쪽 하위 트리 

-정답풀이: 

import sys
input=sys.stdin.readline

n=int(input())
graph=[[] for _ in range(n+1)] 

#루트 확인하는 리스트
isRoot=[0]*(n+1) 
root=0

#거리값 저장하는 리스트
distance=[[] for _ in range(n+1)] 


for _ in range(n):
    parent,left,right=map(int,input().split())
    graph[parent].append(left)
    graph[parent].append(right)
    isRoot[parent]+=1
    if left !=-1:
        isRoot[left]+=1
    if right !=-1:
        isRoot[right]+=1

#루트 설정하기        
for i in range(1,n+1):
	#루트를 제외한 노드는 isRoot==2이다 
    if isRoot[i]==1:
        root=i
        
num=1
def inorder(start,deep): #deep은 레벨에 관련된 값, num은 거리에 관련된 값
    global num
    #왼쪽자식노드에 자식이 있을때
    if graph[start][0]!=-1: 
    	#왼쪽자식노드로 dfs진행 &깊이+1
        inorder(graph[start][0],deep+1)
    #해당 레벨(deep)에 해당하는 거리 삽입
    distance[deep].append(num) 
    num+=1 #이 라인이랑 위 라인만 이해가 가지 않는다#
    if graph[start][1]!=-1:
        inorder(graph[start][1],deep+1)
        
inorder(root,1)
level=1
ans=max(distance[1])-min(distance[1])+1
for i in range(2,n+1):
    if distance[i]:
        small=min(distance[i])
        large=max(distance[i])
        if ans<large-small+1:
            ans=large-small+1
            level=i
print(level)
print(ans)

-가장 이해가 가지 않는 부분: