[BOJ][Python] 2644 촌수계산

[문제]

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

2644번: 촌수계산

 

 

[코드]

#S2_2644 촌수계산.py

#dfs
def dfs(v,depth):
    global graph, visit
    visit[v] = 1
    if v == v2: #도착 노드에 도달한 경우 
        return depth

    for i in range(1, n+1):
        if graph[v][i] == 1 and not visit[i]:
            result = dfs(i,depth+1)
            if result != -1:
                return result

    return -1 #촌수가 존재하지 않는 경우 

#main
n = int(input()) #전체 사람 수
v1, v2 = map(int,input().split()) #촌수를 계산해야 하는 사람
m = int(input()) #관계 개수

graph = [[0] * (n+1) for _ in range(n+1)]
visit = [0] * (n+1)

#관계 입력 받기 
for i in range(m):
    x, y = map(int,input().split()) #x가 y의 부모 
    graph[x][y] = 1
    graph[y][x] = 1

result = dfs(v1,0)
print(result)