백준 1389 케빈 베이컨의 6단계 법칙 (파이썬)

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

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

1. 관계를 양방향으로 저장한다

2. bfs로 모든 경우에 대하여 케빈 베이컨의 수를 구한 후 최소값을 출력

from collections import deque

def bfs(x):
    q.append(x)
    c = [-1 for _ in range(n)]
    c[x] = 0
    while q:
        x = q.popleft()
        for i in a[x]:
            if c[i] == -1:
                c[i] = c[x] + 1
                q.append(i)
    cnt = 0
    for i in range(n):
        if c[i] != -1:
            cnt += c[i]
    return cnt

n, m = map(int, input().split())
a = [[] for _ in range(n)]
q, res, ans = deque(), [], []

for _ in range(m):
    x, y = map(int, input().split())
    x -= 1; y -= 1
    a[x].append(y)
    a[y].append(x)

for i in range(n):
    res.append(bfs(i))

for i in range(n):
    if res[i] == min(res):
        ans.append(i)
print(min(ans)+1)

 

혹은 플로이드-와샬로 모든 경로를 구한 후 최소값을 출력해도 된다

import sys

INF = sys.maxsize
n, m = map(int, input().split())
a = [[INF]*n for _ in range(n)]

for i in range(m):
    x, y = map(int, input().split())
    a[x-1][y-1] = 1
    a[y-1][x-1] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                a[i][j] = 0
            else:
                a[i][j] = min(a[i][j], a[i][k] + a[k][j])

ans = []
for i in a:
    ans.append(sum(i))
for i in range(n):
    if ans[i] == min(ans):
        print(i+1)
        break