[파이썬] 1389 케빈 베이컨의 6단계 법칙

INF = int(1e9)

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

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

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

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            cur = min(graph[a][b], graph[a][k] + graph[k][b])
            graph[a][b] = graph[b][a] = cur

print(sorted([[sum(x), i] for i, x in enumerate(graph)])[0][1])

플로이드-워셜