[백준 1389]https://www.acmicpc.net/problem/1389
문제 조건
케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.
케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.
사람이 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우 그림으로 표현하면
이렇게 된다.
사람의 수와 친구 관계가 입력으로 주어졌을 때 케빈 베이컨의 수가 가장 작은 사람을 구해야 한다.
문제 입력
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다.둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다.
친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 즉, 모든 사람은 친구 관계로 연결되어 있다.
문제 풀기 전 설계
그래프 문제를 풀기 위해 공부하면서 플로이드-워셜 알고리즘이라는 걸 본 적이 있다. 간단히 설명하면 그래프에서 가능한 모든 노드 쌍에 대해 최단거리를 구하는 알고리즘인데, 모든 사람에 대해 자신을 제외한 모든 사람들과의 최소 거리를 합한 것을 비교해야 하는 문제이기 때문에 적절하다고 생각한다.
문제 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken()); // 사람의 수
int m = Integer.parseInt(st.nextToken()); // 관계의 수
int[][] matrix = new int[n + 1][n + 1]; // 그래프를 표현할 2차원 배열
for (int i = 1; i <= n; i++) {
// Floyd-Warshall 알고리즘은 인접하지 않은 노드로 가는 비용의 초기값을 INF(무한대)로 잡아준다.
Arrays.fill(matrix[i], n);
matrix[i][i] = 0;
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine(), " ");
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
matrix[s][e] = 1; // 인접 노드는 비용이 1
matrix[e][s] = 1; // 방향이 없는 그래프이므로 반대로도 저장한다.
}
System.out.println(Floyd_Warshall(matrix));
}
private static int Floyd_Warshall(int[][] arr) {
int[] baconNum = new int[arr.length]; // 각 사람의 베이컨 수를 저장할 배열
for (int m = 1; m < arr.length; m++) { // 거쳐가는 중간 노드
for (int s = 1; s < arr.length; s++) { // 시작 노드
for (int e = 1; e < arr.length; e++) { // 목적 노드
/*
시작 노드 s에서 목적 노드 e로 가는 최단거리를 구하기 위해서
s와 e 사이의 모든 노드 m에 대해 현재 arr[s][e]에 저장된 값과 arr[s][m] + arr[m][e]를 비교하며
arr[s][m] + arr[m][e]가 더 작다면 arr[s][e]값을 그 값으로 바꿔준다.
*/
if (arr[s][e] > arr[s][m] + arr[m][e]) {
arr[s][e] = arr[s][m] + arr[m][e];
}
}
}
}
int minNum = 1; // 베이컨 수가 가장 작은 사람의 번호를 저장할 변수
for (int i = 1; i < baconNum.length; i++) {
for (int j = 1; j < baconNum.length; j++) {
if (i != j) { // 베이컨 수 = 자기 자신을 제외한 모든 사람과의 베이컨 게임 값을 더한다.
baconNum[i] += arr[i][j];
}
}
minNum = (baconNum[i] < baconNum[minNum]) ? i : minNum;
}
return minNum;
}
}문제 풀이
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)에 대한 개념만 있다면 쉽게 이해 가능하다. 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용해 작은 값으로 계속해서 바꿔주면 결국 반복문이 끝났을 때에는 모든 노드쌍의 최단 거리를 알게 된다.
그래프를 표현할 2차원 배열 matrix[][]를 생성하고, 입력값을 받아 인접 노드끼리 연결해준다. 그 후 플로이드-워셜 알고리즘을 이용해 각 노드쌍들에 대해 최단거리를 구하고 1번 노드부터 N번 노드까지 모든 노드에 대한 비용을 더한 값을 배열로 저장한 후 배열의 값이 최소가 되는 인덱스를 출력한다.
Review
플로이드-워셜 알고리즘을 이용해서 해결한 첫 문제이다. 플로이드-워셜 알고리즘은 구현도 간단하고 이해도 쉽지만, 시간 복잡도가 O(V^3)인 점 때문에 조심해서 사용해야 한다. 점점 새로운 알고리즘을 알아가는 게 재밌다.
