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

💡문제접근

• BFS 탐색 알고리즘을 통해 해결할 수 있었다. 양방향 그래프를 그린 다음 거쳐야 하는 단계를 저장한 다음 단계의 총합을 반환하는 방식으로 케빈 베이컨의 수를 구했다.

💡코드(메모리 : 34176KB, 시간 : 64ms)

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

N, M = map(int, input().strip().split())
graph = [[] for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().strip().split())
    graph[a].append(b)
    graph[b].append(a)

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

li = []
for i in range(1, N+1):
    visited = [False] * (N+1)
    li.append(BFS(i))
print(li.index(min(li))+1)

💡소요시간 : 10m