[백준] 2644번 촌수계산

 

 

접근법

- 2명 사이의 촌수를 계산해야하니 DFS로 접근

- 촌수를 계산할 수 없을 때 -1 출력해야하니 check 변수 사용

 

from collections import deque
n = int(input())
a,b = map(int,input().split())
num = int(input())
check = False
graph = [[] for _ in range(n+1)]
visited = [0] *(n+1)
for _ in range(num):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs(graph, c, visited, cnt):
    visited[c] = 1
    global check
    if c == b :
        check = True
        print(cnt)

    for i in graph[c]:
        if visited[i] == 0 :
            dfs(graph, i, visited, cnt+1)
            
dfs(graph,a,visited, 0)

if check == False :
    print(-1)