백준 1389번 : 케빈 베이컨의 6단계 법칙 in Python

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

 

www.acmicpc.net

이 문제는 친구 관계가 주어졌을 때 케빈 베이컨의 수가 가장 적은 사람을 구하는 문제이다. 이떄 어떤 사람의 케빈 베이컨의 수란 각 사람마다 몇 명의 친구를 거쳐야 도달할 수 있는지를 구한 뒤 이를 모두 더한 결과이다.

겉으로 보기에는 복잡해 보이지만, 사실 각 사람마다 BFS를 이용해 다른 사람과의 거리를 구하고, 이를 모두 더하면 케빈 베이컨 수를 구할 수 있다. 그러므로 BFS를 모든 사람에 대해 적용한 뒤 케빈 베이컨 수를 구하고 케빈 베이컨 수가 최소가 되는 사람을 구하면 된다.

이를 코드로 구현하면 다음과 같다.

import sys
from collections import deque
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
# (i, j) 성분이 i번째 사람과 j번째 사람 사이의 거리를 나타내는 행렬
steps = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    graph[B].append(A)
# BFS를 통해 두 사람 사이의 거리를 구한다.
def BFS(i):
    visited = [False for _ in range(N+1)]
    visited[i] = True
    queue = deque()
    queue.append([i, 0])
    while queue:
        u, d = queue.popleft()
        for v in graph[u]:
            if not visited[v]:
                queue.append([v, d+1])
                # 두 사람 사이의 거리를 저장한다.
                steps[i][v] = d+1
                visited[v] = True
for i in range(1, N+1):
    BFS(i)
# 케빈 베이컨 수의 최솟값을 구한다.
min_step = sys.maxsize
for i in range(1, N+1):
    min_step = min(min_step, sum(steps[i]))
# 해당 케빈 베이컨 수를 가지는 사람을 구한다.
for i in range(1, N+1):
    if sum(steps[i]) == min_step:
        print(i)
        break