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

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

풀이

1. 플로이드 워셜 알고리즘으로 각 정점에서의 최단 경로를 계산

2. 각 정점들의 최단 경로의 합을 계산
   ex) 1에서 2, 3, 4, 5로 가는 경로의 합, 2에서 1, 3, 4, 5로 가는 경로의 합, ...

3. 비교 후 더 작은 값을 출력

코드

from sys import stdin
from sys import maxsize

N, M = map(int, stdin.readline().split())

INF = maxsize
graph = [[INF for i in range(N)] for j in range(N)]

for i in range(M):
    a, b = map(int, stdin.readline().split())
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1

for i in range(N):
    graph[i][i] = 0
    
for k in range(N):
    for a in range(N):
        for b in range(N):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

answer = 0
s = INF
for i, data in enumerate(graph):
    if sum(data) < s:
        s = sum(data)
        answer = i + 1
print(answer)