1. 문제 설명

케빈 베이컨의 6단계 법칙

2. 문제 분석

플로이드-워셜 알고리즘을 통해 k번째 노드를 경유지로 사용, i에서 j로 갈 수 있는 거리가 더 짧아진다면 이를 교체한다. 이를 통해 모든 노드에서 다른 모든 노드에 대한 최단 경로를 구할 수 있다.

3. 나의 풀이

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
INF = sys.maxsize
nodes = [[INF for j in range(n+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j: nodes[i][j] = 0

for _ in range(m):
    person1, person2 = map(int, sys.stdin.readline().rstrip().split())
    nodes[person1][person2] = 1
    nodes[person2][person1] = 1

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if nodes[i][j] > nodes[i][k] + nodes[k][j]:
                nodes[i][j] = nodes[i][k] + nodes[k][j]

local_min = INF
smallest_kevin = 0

for i in range(1, n+1):
    sum_kevin = sum(nodes[i][1:])
    if local_min > sum_kevin:
        local_min = sum_kevin
        smallest_kevin = i

print(smallest_kevin)