[백준]230202 문제풀이

2644. 촌수 찾기

# 오답 코드
n = int(input())
a, b = map(int, input().split())
m = int(input())
adj = []
visited = [False] * (n+1)
for i in range(n+1):
    adj.append([0]*(n+1))
for i in range(m):
    x, y = map(int, input().split())
    adj[x][y] = adj[y][x] = 1

def dfs(graph, start, end, visited, cnt):
    if start == end:
        return cnt
    else:
        for i in range(1, n+1):
            if graph[start][i] == 1 and not visited[i]:
                visited[start] = True
                dfs(graph, i, end, visited, cnt+1)
visited[a] = True
res = dfs(adj, a, b, visited, 0)

if res == None:
    print(-1)
else:
    print(res)

DFS 입문 문제로 골라서 답안 코드 복기하면서 혼자 짠 코드인데, 왜인지 계속 오류가 떴다. 아무리 생각해도 논리가 맞는 것 같은데 틀린 이유는 재귀 호출 순서에 대한 이해가 부족했기 때문이었다.

그래프

예제의 그래프를 나타내면 이와 같고, 예제에서 주어진 7과 3의 촌수인 3이 올바르게 출력된다. 하지만 형제 노드인 8이나 9와의 촌수는 2가 출력되어야 하는데 None을 의미하는 -1이 출력된다. 왜 그럴까?

7과 9의 관계를 찾을 때 호출되는 순서

return 값을 하나씩 append해서 순서대로 보면 감이 온다. 원래 답인 2를 찾았을 때 재귀함수가 멈추는 게 내 예상이었지만, 먼저 호출된 None에 의해 정답이 씹히게 된다.

7과 8의 관계를 찾을 때 호출되는 순서

7과 3의 관계를 찾을 때 호출되는 순서

다른 값들을 찾을 때 호출되는 순서를 보면 더 명확하게 알 수 있다. 가장 깊게, 가장 먼저(Depth First!) 호출되는 3으로 시작해 3, 1, 8, 9, 2 순서로 호출된다. 따라서 가장 큰 촌수의 노드를 찾는 게 아닌 이상 return을 통해서는 답을 찾을 수 없게 된다.

n = int(input())
a, b = map(int, input().split())
m = int(input())
adj = []
visited = [False] * (n+1)
for i in range(n+1):
    adj.append([0]*(n+1))
for i in range(m):
    x, y = map(int, input().split())
    adj[x][y] = adj[y][x] = 1

def dfs(graph, start, end, visited, cnt):
    global res
    visited[start] = True
    if start == end:
        res = cnt
    else:
        for i in range(1, n+1):
            if graph[start][i] == 1 and not visited[i]:
                dfs(graph, i, end, visited, cnt+1)

res = 0
dfs(adj, a, b, visited, 0)

if res == 0:
    print(-1)
else:
    print(res)

위의 코드에서 cnt를 return하는 식이 아닌, return 없이 전역변수에 답을 할당해주는 식으로 하면 해결된다. global로 전역변수를 끌고와서 함수 내에서 처리하는 발상은 물론 컨닝했지만... 덕분에 나름 재귀와 dfs에 대해 깊게 고민할 수 있었던 시간이었다.