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

🚩 그래프이론, 그래프탐색, BFS

 

thinking

문제를 읽어보니 BFS여서 BFS로 풀었다.

인접리스트를 만들어준 후, 1번부터 순회하면서 케빈베이컨수를 카운팅한 후 리스트에 넣고

그 리스트에서 가장 작은 값의 인덱스를 출력했다.

 

코드

from collections import deque

def BFS(i):
    visited = [0] * (N+1)
    queue.append(i)
    visited[i] = 1
    while queue:
        t = queue.popleft()
        for v in edge_list[t]:
            if not visited[v]:
                visited[v] = visited[t]+1
                queue.append(v)
    return sum(visited)


N, M = map(int, input().split())  # N:유저의 수, M: 친구관계 수
edge_list = [[] for _ in range(N+1)]
for _ in range(M):
    s, e = map(int, input().split())
    edge_list[s].append(e)
    edge_list[e].append(s)

queue = deque()
res = []
for i in range(1, N+1):
    res.append(BFS(i))

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