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

그래프는 2차원 배열이나 collections 라이브러리의 defaultdict() 타입으로 선언해준다. 

 

bfs 방식으로 그래프를 탐색하되, 각 시작점마다 dist 배열을 선언해서 해당 노드를 탐색하기까지 몇 개의 노드를 거쳤는지를 표시해주고, sum()으로 그 거리들을 모두 더해준다. 

 

이때 sum() 0번째 노드를 제외하는 이유는 노드는 1번째 부터 N번째까지 있기 때문이다. 

 

마지막으로 각 노드마다 get_dist라는 bfs 탐색을 하는 함수를 호출하면서 값을 비교하고, 거리의 합이 더 작은 노드를 min_number 값으로 바꿔 주면서 for문을 1번 순회하면 된다. 

 

 

풀이

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

N, M = map(int, input().split())
graph = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def get_dist(num):
    dist = [-1] * (N+1)
    dist[num] = 0
    Q = deque([num])
    while Q:
        elem = Q.popleft()
        for node in graph[elem]:
            if dist[node] == -1:
                Q.append(node)
                dist[node] = dist[elem] + 1
    return sum(dist[1:])

min_dist = sys.maxsize
min_number = 101

for i in range(1, N+1):
    bacon_dist = get_dist(i)
    if bacon_dist < min_dist:
        min_dist = bacon_dist
        min_number = i
    elif bacon_dist == min_dist:
        min_number = min(i, min_number)
        
print(min_number)