[백준] 2644 : 촌수계산 python

 

전에 풀었던 케빈 베이컨의 6단계 법칙 문제에서 사용했던 방법을 그대로 썼다.

모든 정점에 대해 bfs를 수행할 필요는 없고, 촌수를 계산해야 하는 번호에 대해서만 bfs를 수행해주면 된다.

 

 

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

n = int(input())
a,b=map(int,input().split())
m=int(input())

graph = [[]for i in range(n+1)]
result = []

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

def bfs(start):
    visited = [False]*(n+1)
    num = [0]*(n+1)
    queue = deque()
    queue.append(start)
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
                num[i] = num[v]+1
    return num

res = bfs(a)

if res[b]==0:
    print(-1)
else:
    print(res[b])