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

import sys

def solution():
    N, M = map(int, sys.stdin.readline().split())
    relation = [[10000 for _ in range(N)] for _ in range(N)]

    for _ in range(M):
        start, end = map(int, sys.stdin.readline().split())
        relation[start - 1][end - 1] = 1
        relation[end - 1][start - 1] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if relation[i][j] > relation[i][k] + relation[k][j]:
                    relation[i][j] = relation[i][k] + relation[k][j]

    minRelation = 314159265
    ret = 0
    for idx, rel in enumerate(relation):
        val = sum(rel)

        if val < minRelation:
            minRelation = val
            ret = idx
    print(ret+1)

solution()

https://www.acmicpc.net/problem/1389