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

플로이드 워셜 알고리즘으로 풀었다.

그래프에 친구들 간 관계의 비용을 계산한 후, 저장한다.

그래프에서 각 사람별로 친구들간 관계의 비용이 가장 낮은 사람을 구해준다.

 

import sys
from copy import deepcopy
from math import inf

n, m = map(int,input().split())
graph = [[inf]*n for _ in range(n)]
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
def floyd(graph):
    d = deepcopy(graph)
    for a in range(n):
        for b in range(n):
            for c in range(n):
                d[b][c] = min(d[b][c], d[b][a] + d[a][c])
    return d
d = floyd(graph)

mini = sum(d[-1])
mini_p = n
for i in range(n-2,-1,-1):
    if mini >= sum(d[i]):
        mini_p = i+1
        mini = sum(d[i])
print(mini_p)