[BOJ/Python] 백준 2644번 - 촌수계산

백준 #2644 촌수계산

2644번: 촌수계산

from collections import deque
import sys
input = sys.stdin.readline

def bfs():
  q = deque()
  q.append(p1)
  while(q):
    u = q.popleft()
    if u == p2:
      return visited[p2]
    for w in family[u]:
      if visited[w] == 0:
        if w == p1:
          continue
        visited[w] = visited[u] + 1
        q.append(w)
    
n = int(input())   # 사람의 수
p1, p2 = map(int, input().split())   # 촌수 계산할 서로 다른 두 사람의 번호
m = int(input())   # 부모 자식들 간의 관계의 개수
family = [[] for _ in range(n+1)]
for _ in range(m):
  v1, v2 = map(int, input().split())
  family[v1].append(v2)
  family[v2].append(v1)

visited = [0 for _ in range(n+1)]
cnt = bfs()
if cnt:
  print(cnt)
else:
  print(-1)

너비우선탐색으로 최단경로 길이만 계산하면 되는 문제! 촌수를 계산할 시작 번호에서 끝 번호가 나올 때까지 탐색을 진행하여 이동 횟수를 visited 리스트에 담아준다. 끝 번호가 나오면 이동 횟수 return