안녕하세요! 오늘은 코딩 테스트에서 자주 출제되는 알고리즘 문제 중 하나인 “케빈 베이컨의 6단계 법칙”에 대해 알아보겠습니다. 이 문제는 다양한 그래프 이론의 개념을 활용하여 해결할 수 있으며, 특히 너비 우선 탐색(BFS)이나 깊이 우선 탐색(DFS)과 같은 기본적인 탐색 알고리즘을 연습할 수 있는 좋은 기회를 제공합니다.
1. 문제 설명
케빈 베이컨의 6단계 법칙은 유명한 사회 관계망 이론 중 하나로, 두 사람 사이의 관계를 통한 연결고리가 6단계 이내에 존재한다는 이론입니다. 이를 코드로 구현해보는 문제입니다.
문제는 다음과 같습니다:
주어진 N명의 사용자와 그들 간의 관계가 주어질 때, 각 사용자 간의 케빈 베이컨의 점수를 계산하고, 가장 점수가 낮은 사용자를 출력하는 프로그램을 작성하시오. 점수는 해당 사용자와의 최단 거리의 합입니다.
2. 입력 형식
첫 줄에는 사용자 수 N(1 ≤ N ≤ 100)과 관계의 수 M(0 ≤ M ≤ 4,900)이 주어집니다.
다음 M개의 줄에는 두 정수 a, b가 주어지며, 이는 사용자 a와 b가 서로 친구라는 것을 나타냅니다.
3. 출력 형식
케빈 베이컨 점수가 가장 낮은 사용자의 번호를 출력합니다. 점수가 같은 경우에는 가장 번호가 작은 사용자를 출력합니다.
4. 문제 해결 과정
이 문제를 풀기 위해선 다음 단계를 따라야 합니다:
4.1. 그래프 생성
먼저 각 사용자와 친구 관계를 나타내는 그래프를 인접 리스트 형태로 생성합니다. 이 그래프는 딕셔너리나 리스트를 사용하여 표현할 수 있습니다.
graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
4.2. BFS 또는 DFS 구현
각 사용자에 대해 BFS 또는 DFS를 통해 다른 사용자와의 최단 거리를 계산합니다. BFS가 최단 경로를 보장하기 때문에 이 문제에는 BFS를 사용하는 것이 더 적합합니다.
def bfs(start, graph):
queue = [start]
visited = {start: 0}
while queue:
current = queue.pop(0)
for neighbor in graph[current]:
if neighbor not in visited:
visited[neighbor] = visited[current] + 1
queue.append(neighbor)
return sum(visited.values())
4.3. 점수 계산
모든 사용자의 케빈 베이컨 점수를 계산합니다. BFS 결과를 이용하여 점수를 저장하고, 가장 낮은 점수를 찾습니다.
min_score = float('inf')
user_with_min_score = -1
for user in range(1, N + 1):
score = bfs(user, graph)
if score < min_score:
min_score = score
user_with_min_score = user
elif score == min_score:
user_with_min_score = min(user_with_min_score, user)
5. 전체 코드
이제, 위 과정을 통합한 전체 코드를 작성해보겠습니다.
from collections import deque
def bfs(start, graph):
queue = deque([start])
visited = {start: 0}
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if neighbor not in visited:
visited[neighbor] = visited[current] + 1
queue.append(neighbor)
return sum(visited.values())
def find_kevin_bacon(graph, n):
min_score = float('inf')
user_with_min_score = -1
for user in range(1, n + 1):
score = bfs(user, graph)
if score < min_score:
min_score = score
user_with_min_score = user
elif score == min_score:
user_with_min_score = min(user_with_min_score, user)
return user_with_min_score
# 입력
N, M = map(int, input().split())
graph = {i: [] for i in range(1, N + 1)}
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# 결과 출력
result = find_kevin_bacon(graph, N)
print(result)
6. 코드 설명
코드는 주어진 N과 M 값을 입력받고, 친구 관계를 바탕으로 그래프를 구성한 다음, 각 사용자에 대한 BFS를 통해 케빈 베이컨 점수를 계산합니다. 마지막으로 가장 점수가 낮은 사용자의 번호를 출력합니다. 이 문제를 통해 그래프 이론과 BFS 알고리즘에 대한 좋은 연습이 될 것입니다.
7. 성능 분석
이 알고리즘의 시간 복잡도는 O(V + E)로, V는 정점(사용자)의 수, E는 간선(관계)의 수입니다. 이 경우 N이 100이라고 가정할 때, 최악의 경우 4900개의 관계를 가질 수 있으므로, 총 100번의 BFS 호출 시 약 495,000번의 탐색이 일어납니다. 이는 주어진 시간 내에 충분히 처리 가능한 범위에 속합니다.
8. 결론
케빈 베이컨의 6단계 법칙을 활용한 이 문제는 그래프 이론의 기초를 다지고, BFS의 활용법을 익힐 수 있는 좋은 기회입니다. 다양한 변형 문제를 통해 추가적으로 연습한다면 알고리즘적 사고를 더욱 재고할 수 있을 것입니다. 앞으로도 다양한 문제를 통해 코딩 테스트 준비를 지속적으로 해나가시길 바랍니다!
감사합니다!