[Python] 백준 / silver / 2644 : 촌수계산

문제 링크 : https://www.acmicpc.net/problem/2644

둘째 주 목요일은 BFS / DFS 푸는 날. 너비 우선 탐색을 진행하면서 원하는 사람을 만났으면 break 하고 find 값을 True로 변경했다. 너비 우선 탐색을 모두 마쳤음에도 find 가 True로 변하지 않는다면, 찾지 못한 것이므로 -1을 출력했다. 촌수를 계산하기 편하게 큐에 num 값을 담아 계산했다.

파이썬 코드

from collections import deque
import sys
n = int(sys.stdin.readline())
A, B = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
visit = [False] * (n+1)
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

find = False
q = deque()
q.append((A,0))
visit[A] = True

while q:
    now, num = q.popleft()

    for node in graph[now]:
        if not visit[node]:
            q.append((node, num+1))
            visit[node] = True
            if node == B:
                find = True
                print(num+1)
                break

if not find:
    print(-1)