[백준] 1389번, 케빈 베이컨의 6단계 법칙 (Python)

문제

https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

 

코드

import collections
import sys

INF = sys.maxsize
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

queue = collections.deque()

def bfs(index):
    queue.append(index)
    while queue:
        cur = queue.popleft()
        visited[cur] = True
        for next in graph[cur]:
            if visited[next] == False:
                visited[next] = True
                distance[next] = distance[cur] + 1
                queue.append(next)

result = [INF]
for i in range(1,n+1):
    distance = [0 for _ in range(n+1)]
    visited = [False for _ in range(n+1)]   
    bfs(i)
    result.append(sum(distance))

print(result.index(min(result)))

정점마다 bfs를 돌아서 다른 정점까지에 거리에 합이 가장 작은 수를 구하는 문제이다.

 

result에 distance를 구한다음 합을 넣어준뒤에 가장 작은 인덱스 값을 구하면된다.

 

result index에 쉽게 접근하기 위해서 0인덱스에는 maxsize만큼 값을 넣어놓는다.