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

CodeWisp·2025년 4월 9일

BFS 백준 플로이드 워셜

문제 정보

ℹ️ 문제 정보

문제명: 백준 1389번 - 케빈 베이컨의 6단계 법칙
난이도: 실버 1 (solved.ac 기준)
태그: 그래프 탐색 (BFS, 플로이드-워셜), 최단 거리

문제 설명 요약

케빈 베이컨 게임 은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.
케빈 베이컨 수 는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

유저의 수와 친구 관계가 입력으로 주어졌을 때,
케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하라.

접근 방식

케빈 베이컨 수에 대한 정의

문제에서 얘기하는 케빈 베이컨 수를 "나의 언어" 로 풀어내자면,
한 사람이 모든 사람과 얼마나 가까운지 나타내는 거리의 총합이라 볼 수 있다.

관계가 1단계씩 연결되어 있다는 점에서,
결국 그래프 상의 최단 거리 합을 구하라는 문제이다.
최단 거리? 그렇다면?

처음 떠오른 생각

직관적으로는, 모든 사람 간의 최단 거리를 구해야 한다는 점에서,
플로이드-워셜이 먼저 떠올랐다.

중간에 경유지를 하나씩 추가하면서 거리 정보를 갱신해 나가면,
결국 dist[i][j] 형태로 모든 정점 간의 최단 거리를 얻을 수 있다.

그 상태에서 각 사용자마다 sum(dist[user][1:])를 계산해보면,
가장 거리가 짧은 사람이 자연스럽게 정답이 된다. 💡 풀이 1

다른 방법도 가능하지 않을까?

간선의 가중치가 모두 1이라는 점에서,
각 사람마다 BFS를 한 번 돌리는 방식으로도 최단 거리를 구할 수 있다!

물론 구현은 조금 더 번거롭지만,
플로이드-워셜 없이 전체 거리 합을 계산할 수 있는 방식이라 흥미로웠다.

그래서 같은 문제를 다른 방식으로 바라보는 연습 삼아,
BFS 풀이도 함께 시도해보았다. 💡 풀이 2

📌 실전 구현 팁

입력 받은 그래프 작성 시에 무방향을 인지하기 (u → v, v → u)
입력받은 정점이 1부터 N까지이니, 1-based index 로 구현
위의 방식으로 작성했다면, sum 계산 시에 슬라이스 범위 체크 (sum(dist[i][1:])
방문 처리를 위한 배열로 dist를 쓰면, 추가적인 visited 없이도 간결하게 구현 가능

💡 풀이 1 - 플로이드-워셜 기반

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

각 정점 k 를 경유지로 설정하여,
기존보다 start → k → end 경로가 더 짧은지 확인하는 방식을 이용하면
점진적으로 더 짧은 경로로 갱신된다.
결과적으로, 모든 정점 쌍에 대해 최단 거리를 얻을 수 있다.

import sys

input = sys.stdin.readline

V, E = map(int, input().split())
dist = [[0 if u == v else float("inf") for v in range(V + 1)] for u in range(V + 1)]
users = range(1, V + 1)

for _ in range(E):
    u, v = map(int, input().split())
    dist[u][v] = 1
    dist[v][u] = 1

# 플로이드-워셜
for k in users:
    for u in users:
        for v in users:
            dist[u][v] = min(dist[u][k] + dist[k][v], dist[u][v])

# 케빈 베이컨의 수가 가장 작은 사람 구하기
min_user = 0
min_KB = float("inf")

for user in users:
    KB = sum(dist[user][1:])
    if min_KB > KB:
        min_user = user
        min_KB = KB

print(min_user)

💡 풀이 2 - BFS 기반

1389 - 케빈 베이컨의 6단계 법칙(2).py

간선 가중치가 모두 1 이라고 가정 시,
BFS는 자연스럽게 최단 거리 탐색이 가능한 알고리즘이다.
따라서, 별도의 비용 계산 없이 depth 만으로 거리 누적이 가능하다.

from collections import deque
import sys

input = sys.stdin.readline

V, E = map(int, input().split())
graph = {i: [] for i in range(1, V + 1)}

for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 케빈 베이컨의 수가 가장 작은 사람 구하기
min_user = 0
min_KB = float("inf")

# 모든 user에 대해 BFS를 돌려서 케빈 베이컨 수 구하기
for user in range(1, V + 1):
    dist = [-1] * (V + 1)
    dist[user] = 0
    queue = deque([user])

    # BFS
    while queue:
        u = queue.popleft()

        for v in graph[u]:
            if dist[v] != -1:
                continue

            dist[v] = dist[u] + 1
            queue.append(v)

    KB = sum(dist[1:])
    if min_KB > KB:
        min_user = user
        min_KB = KB

print(min_user)

정리 & 회고

이 문제는 처음부터 "한 정점으로부터 모든 정점까지의 최단 거리" 를 구해야 한다고 느꼈다.
그래서 단순히 사람 별 최단 거리를 구하는 것보다,
처음부터 모든 경로의 최단 거리를 다 구해놓는 방식의 구현이 당연하다고 느꼈다.
그러다 보니, 자연스럽게 플로이드-워셜로 접근하게 됐다.
입력 크기가 작아서 시간 복잡도의 영향을 덜 받으니까, 최적이라고 생각했다.
그럼에도 불구하고 BFS 로 한번 더 풀어본 이유는,
간선 가중치가 1이라는 조건만 붙인다면, BFS만으로 최단 거리를 쉽게 판단할 수 있었기 때문이다.
구현은 좀 더 복잡해지나, 성능 면에서는 직관적으로 훨씬 이득이기에 확인하고 싶었다.

두 가지 방법을 비교해보니,
이 문제에서는 플로이드-워셜이 좀 더 직관적이고, 구현도 단순했다.
다만, 제한시간이 좀 더 타이트했다면 BFS를 선택했을 것 같다.
문제를 "거리" 관점으로 이해하기에 좋은 연습이 됐다.
문제 조건 덕분에 한 문제를 두 가지 방법으로 풀어보면서,
내 사고의 유연함을 점검할 수 있는 좋은 기회가 됐다.