[파이썬]백준 1389 케빈 베이컨의 6단계 법칙

링크

백준 1389 케빈 베이컨의 6단계 법칙

모든 경우를 다 탐색해야 하며 그 중 최솟값을 구해야 하기 때문에 보자마자 bfs로 접근해야겠다고 생각했다.

bfs로 거리를 구하는 방법을 사용하되 약간 응용했다.
인접리스트를 받을때 출발노드와 도착노드를 받아왔고 큐에 노드를 추가할때도 출발노드와 도착노드를 함께 넣어주었다.
이를 활용해 도착노드까지의 거리를 출발노드까지의 거리+1 로 계산해주며 케빈베이컨수를 계산했다.

정답 코드

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

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
bacon = 0xfffffff
ans = 101
for i in range(M):
    u, v = map(int, input().split())
    adj[u].append([u, v])
    adj[v].append([v, u])

for i in range(1, N + 1):
    dis = [-1] * (N + 1)
    dis[0], dis[i] = 0, 0
    q = deque()
    q.extend(adj[i])
    while q:
        s, e = q.popleft()
        if dis[e] == -1:
            dis[e] = dis[s] + 1
            q.extend(adj[e])

    if sum(dis) < bacon:
        bacon = sum(dis)
        ans = i

print(ans)

알게된 것👨‍💻

• bfs의 응용