촌수 계산

풀이

 그래프 탐색, BFS 문제다. 간단하게 start 지점에서 1칸 떨어지면 1촌, 2칸 떨어지면 2촌, 3칸 떨어지면 3촌이다. 예제를 트리 형식으로 표현하면 문제를 파악하는 데 도움이 된다. 트리를 보면 7과 3은 3칸 떨어졌으니 3촌 관계가 된다.

예제 입력 1
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

from collections import deque
n = int(input())
x,y = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]

for i in range(m):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

queue = deque([[x, 1]])
visited[x] = True
while queue:
    s, c = queue.popleft()
    for i in graph[s]:
        if visited[i] == False:
            if i == y:
                print(c)
                exit(0)
            visited[i] = True
            queue.append([i, c+1])
    c += 1
print(-1)

시간복잡도 : O(V+E)