BOJ-1389 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389

문제 소개

케빈 베이컨 수는 케빈 베이컨 게임을 했을 때 나오는 단계의 합이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구한다.

문제 풀이

bfs를 이용하여 풀이하였다.

함수 bfs는 큐에 정점을 삽입할 때 몇 단계를 거쳐서 도달했는지 그 비용도 같이 튜플 형태로 삽입하며, 방문하지 않은 정점을 방문할 때마다 변수 acc에 비용을 누적시킨 후 마지막으로 acc를 반환한다.

모든 정점으로부터의 bfs 수행 후, acc들 중 최솟값을 가지는 정점 번호를 출력한다.

코드

from sys import stdin
from collections import deque
input = lambda: stdin.readline().rstrip()


def bfs(start):
    queue = deque([(start, 1)])
    visited[start] = True
    acc = 0
    while queue:
        t, cost = queue.popleft()
        # print(f"{t}를 큐에서 꺼냄")
        for i in graph[t]:
            if not visited[i]:
                queue.append((i, cost + 1))
                visited[i] = True
                acc += cost
                # print(f"{i}까지 비용 : {cost}")
    # print(acc, end="\n\n")
    return acc


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)

# bfs 수행
scores = []
for i in range(1, n + 1):
    visited = [False] * (n + 1)
    scores.append(bfs(i))

# 가장 작은 acc를 갖는 사람의 번호 출력
print(scores.index(min(scores)) + 1)

주석 처리된 print문들을 통해 동작을 살펴볼 수 있다.