안녕하세요! 이번 포스트에서는 자바를 활용하여 ‘케빈 베이컨의 6단계 법칙’에 대해 알아보겠습니다. 이 법칙은 사회적 연결망 이론에서 파생된 것으로, 두 사람 사이에 여섯 단계 이하로 연결될 수 있다는 내용을 담고 있습니다. 우리는 이를 알고리즘 문제로 변형하여 구현해 보도록 하겠습니다.
문제 설명
우리가 해결해야 할 문제는 다음과 같습니다. 주어진 친목 관계를 기반으로 한 그래프에서, 특정 두 사람 간의 최단 경로를 찾는 것입니다. 이사람들이 서로 연결된 정도에 따라 “케빈 베이컨 지수”를 계산하여, 이를 통해 누가 서로 연결되는지를 알아보겠습니다.
문제 정의
주어진 친구 관계가 리스트 형태로 주어질 때, 모든 사람에 대해 ‘케빈 베이컨 지수’를 계산하고, 가장 낮은 지수를 가진 사람을 찾아 출력하는 알고리즘을 작성하시오.
입력 형식
- 첫 줄에는 사람의 수 N (1 ≤ N ≤ 1000)이 주어진다.
- 다음 줄에는 친구 관계의 수 M (0 ≤ M ≤ 100,000)이 주어진다.
- 이후 M줄에 걸쳐 친구 관계를 나타내는 두 수 A, B (1 ≤ A, B ≤ N)가 주어진다. 이는 A와 B가 친구임을 뜻한다.
출력 형식
모든 사람에 대해 케빈 베이컨 지수를 계산하고, 그 값이 가장 낮은 사람의 번호를 출력하시오. 만약 두 사람의 케빈 베이컨 지수가 동일하다면 작은 번호를 가진 사람을 출력해야 합니다.
문제 해결 과정
이 문제를 해결하기 위해 아래의 단계를 따릅니다:
1단계: 그래프 구현
친구 관계는 그래프의 형태로 표현할 수 있습니다. 각 사람을 정점으로 하고, 두 사람 간의 친구 관계를 간선으로 표현합니다. 여기서 인접 리스트를 사용하여 그래프를 구현해 보겠습니다.
import java.util.*;
public class KevinBaconGame {
static List> graph;
static int[] distance;
public static void main(String[] args) {
// 여기서 입력 처리 및 그래프 초기화를 할 것입니다.
}
}
2단계: BFS 알고리즘 구현
케빈 베이컨 지수를 계산하기 위해 BFS를 사용합니다. BFS는 최단 경로를 찾는 데 매우 효과적입니다. 각 사람으로부터 BFS를 실행하여 모든 친구들의 최단 경로를 계산할 수 있습니다.
static int bfs(int start) {
Queue queue = new LinkedList<>();
boolean[] visited = new boolean[graph.size()];
Arrays.fill(distance, Integer.MAX_VALUE);
queue.offer(start);
visited[start] = true;
distance[start] = 0;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
distance[neighbor] = distance[current] + 1;
queue.offer(neighbor);
}
}
}
int totalDistance = 0;
for (int d : distance) {
totalDistance += d;
}
return totalDistance;
}
3단계: 결과 계산 및 출력
모든 사람에 대하여 BFS를 실행하고 케빈 베이컨 지수를 계산한 뒤, 최종적으로 가장 낮은 지수를 가진 사람을 찾습니다. 이 과정에서 사람의 번호와 지수를 저장하여 비교합니다.
for (int i = 1; i <= N; i++) {
int baconIndex = bfs(i);
// 여기에 케빈 베이컨 지수를 저장하는 로직이 들어갑니다.
}
// 최종 결과 출력 부분입니다.
코드 전체보기
import java.util.*;
public class KevinBaconGame {
static List> graph;
static int[] distance;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
graph = new ArrayList<>();
distance = new int[N + 1];
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
int A = scanner.nextInt();
int B = scanner.nextInt();
graph.get(A).add(B);
graph.get(B).add(A);
}
int minBaconIndex = Integer.MAX_VALUE;
int resultPerson = 0;
for (int i = 1; i <= N; i++) {
int baconIndex = bfs(i);
if (baconIndex < minBaconIndex) {
minBaconIndex = baconIndex;
resultPerson = i;
}
}
System.out.println(resultPerson);
}
static int bfs(int start) {
Queue queue = new LinkedList<>();
boolean[] visited = new boolean[graph.size()];
Arrays.fill(distance, Integer.MAX_VALUE);
queue.offer(start);
visited[start] = true;
distance[start] = 0;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
distance[neighbor] = distance[current] + 1;
queue.offer(neighbor);
}
}
}
int totalDistance = 0;
for (int d : distance) {
totalDistance += d;
}
return totalDistance;
}
}
결론
이번 포스트에서는 케빈 베이컨의 6단계 법칙을 바탕으로 친구 간의 관계를 확인하고 케빈 베이컨 지수를 통해 가장 가까운 사람을 찾는 알고리즘을 구현해 보았습니다. BFS를 통해 최단 경로를 효과적으로 계산하여, 친구 관계 그래프를 탐색하는 방법을 배울 수 있었습니다. 자바를 사용한 코딩테스트 문제 해결 과정에 대해 좀 더 깊이 있는 이해를 돕기 위해 이와 같은 알고리즘 문제를 여러 번 풀어보시기를 권장합니다.