[백준] 1389 : 케빈 베이컨의 6단계 법칙 python

 

n개의 정점에 대해 bfs를 수행할 때마다 num이라는 배열에 연관된 정점사이의 거리를 기록하고,

num의 총합을 result라는 리스트에 append해준다.

 

1-3, 3-2, 2-4, 4-5이렇게 연결되어있을 때

1번을 시작 정점으로 bfs를 수행하면서

1번의 인접정점인 3,4의 거리가 1이라는 것을 num[3], num[4]에 기록해준다.

 

그리고 3번을 시작 정점으로 다시 bfs를 수행할 때

3번의 인접 정점인 2번자리 num[2]에는 num[3]+1을 저장하는 방식으로 하면

1번과 연관이 있는 각 정점간의 거리를 알 수 있다.

 

 

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

n,m = map(int,input().split())
graph=[[]for i in range(n+1)]
result=[]

for i in range(m):
    s,e = map(int,input().split())
    graph[s].append(e)
    graph[e].append(s)
    
def bfs(start):
    visited = [False]*(n+1)
    num = [0]*(n+1)
    queue = deque()
    queue.append(start)
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                num[i] = num[v]+1
    return sum(num)

for i in range(1,n+1):
    result.append(bfs(i))

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