[Python/파이썬] 백준 1389 - 케인 베이컨의 6단계 법칙

문제 설명

 

입력과 출력

 

입출력 예제

 

---

풀이 코드

 

 

아래 표 처럼 각 노드에서 출발하여 해당 노드와 연결된 노드까지의 거리를 구한 뒤, 총합이 가장 높은 노드를 출력하는 문제이다.

케빈 베이컨의 수	0	1	2	3	4	5
1번 노드	0	0	2	1	1	2
2번 노드	0	2	0	1	2	3
3번 노드	0	1	1	0	1	2
4번 노드	0	1	2	1	0	1
5번 노드	0	2	3	2	1	0

 

 

정답 코드

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 유저 수, 친구관계 수

relationship = [[] for _ in range(n + 1)]

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

def bfs(start):
    distance = [0] * (n + 1)
    visited = [False] * (n + 1)
    q = deque()
    q.append(start)
    visited[start] = True
    
    while q:
        cur = q.popleft()

        for next in relationship[cur]:
            if not visited[next]:
                distance[next] = distance[cur] + 1
                visited[next] = True
                q.append(next)
    return sum(distance)

cnt = []
for start in range(1, n + 1):
    cnt.append(bfs(start))

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