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

-Code

from collections import deque

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

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

kevin = []

def bfs(start, goal):
    visited = [False] * (n + 1)
    visited[start] = True
    dq = deque([(start, 0)])

    while dq:
        now, d = dq.popleft()

        if now == goal:
            return d

        for nxt in users[now]:
            if not visited[nxt]:
                visited[nxt] = True
                dq.append((nxt, d + 1))

def get_kevin(start):
    ans = 0

    for i in range(1, n + 1):
        if i != start:
            ans += bfs(start, i)

    return ans

for i in range(1, n + 1):
    kevin.append(get_kevin(i))

print(kevin.index(min(kevin)) + 1)

bfs 강의를 들으며 해결해 봤는데 익숙하지 않아 한 부분씩 잘못 작성해서 해결하긴 했지만 다음에 다시 풀어봐야 할 것 같습니다.