백준 1389번: 케빈 베이컨의 6단계 법칙 (BFS)

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

각 사람을 노드로, 관계를 간선으로 표현할 수 있는 그래프 문제. 너비 우선 탐색인 bfs함수를 만들어서 문제를 풀었다. bfs는 파이썬에서 일반적으로 deque 객체를 queue로 이용하여 구현한다.

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

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


def bfs(graph, start):
    num = [0] * (N+1)
    queue = deque()
    visited[start] = 1
    queue.append(start)

    while queue:
        t = queue.popleft()
        for i in graph[t]:
            if visited[i] == 0:
                num[i] = num[t]+1
                queue.append(i)
                visited[i] = 1
    return sum(num)


result = list()
for i in range(1,N+1):
    visited = [0] * (N+1)
    result.append(bfs(graph, i))

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

간선의 수가 비교적 밀도가 낮은 그래프의 경우는 인접 행렬보다는 인접 리스트로 그래프를 구현하는 것이 좋다는 글을 봤다. 노드 수 맥시멈 1백 개, 간선 수 맥시멈 5천 개인 경우 위 코드를 실행시켰을 때 68ms가 걸렸다.