백준 촌수계산 2644 DFS

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

• 노드가 연결된 그래프, 방문배열, 결과값 저장할 장소를 만든다
• dfs에서 매개변수로 방문할 노드와 몇 번째 방문인지를 나타내는 cnt를 받는다
• 만약 방문 중인 노드와 타겟 노드와 같다면 현재 몇 번째 방문인지를 result에 append한다
• 그렇지 않을 경우 재귀로 dfs를 호출한다
• 만약 result 안에 아무것도 없으면 아무 관계도 아니므로 -1을 리턴하고 값이 있으면 result[0]의 값을 리턴한다.
• dfs를 재귀로 구현할 때 cnt를 어떻게 내보내야할지 고민이었는데, 이렇게 result라는 global 변수를 지정해두고 cnt를 result에 저장해주면 된다는 점을 배웠다

N = int(input())
x, y = map(int, input().split())
M = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
result = []

for _ in range(M):
    p, c = map(int, input().split())
    graph[p].append(c)
    graph[c].append(p)

def dfs(v, cnt):
    if visited[v]:
        return
    
    cnt += 1
    visited[v] = True

    if v == y:
        result.append(cnt)

    for i in graph[v]:
        if not visited[i]:
            dfs(i, cnt)

dfs(x,0)

if len(result) == 0:
  print(-1)
else:
  print(result[0]-1)