백준 1389번 : 케빈 베이컨의 6단계 법칙 (플로이드-워셜)
이번 문제는 전형적인 플로이드-워셜 알고리즘 문제로, 케빈 베이컨의 6단계 법칙을 활용해 각 정점 중 최단거리로 연결된 모든 정점까지 갈 수 있는 거리가 가장 적은 정점을 찾는 문제이다.
케빈 베이컨은 모든 사람들은 최대 6 단계 이내에서 서로 아는 사람으로 연결될 수 있다는 법칙인데, 문제의 예시는 설명에 잘 나와 있기 때문에 백준 : 케빈 베이컨의 6단계 법칙으로 가서 확인해보는 것이 좋다.
테스트 케이스를 예를 들면
1
2
3
4
5
6
5 5
1 3
1 4
4 5
4 3
3 2
가장 첫 줄인 유저의 수, 관계의 수 다음의 연결 정보를 바탕으로 다음을 유추해 볼 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1. 정점 1
- 1부터 2까지 1-3-2 / 2단계
- 1부터 3까지 1-3 / 1단계
- 1부터 4까지 1-4 / 1단계
- 1부터 5까지 1-5-4 2단계
- 케빈 베이컨 수 = 6
2. 정점 2
- 2부터 1까지 2-3-1 / 2단계
- 2부터 3까지 2-3 / 1단계
- 2부터 4까지 2-3-4 / 2단계
- 2부터 5까지 2-3-4-5 / 3단계
- 케빈 베이컨 수 = 8
3. 정점 3
- 3부터 1까지 3-1 / 1단계
- 3부터 2까지 3-2 / 1단계
- 3부터 4까지 3-4 / 1단계
- 3부터 5까지 3-4-5 / 2단계
- 케빈 베이컨 수 = 5
...
이런 식으로 진행되고, 가장 적은 케빈 베이컨을 가진 정점은 3과 4이므로 더 작은 수인 3이 리턴되어야한다.
이 문제를 풀기 위해 음수 순환 사이클이 없는 그래프에서 모든 점에서 모든 점까지의 최단거리를 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용할 수 있다.
이 플로이드-워셜 알고리즘은 다익스트라 알고리즘과 달리 거쳐가는 중간 노드를 기준으로 최단 거리를 구한다.
또한, 다익스트라와는 다르게 음의 가중치를 갖는 간선이 있어도 활용할 수 있다.
단, 합이 음수 가중치를 갖는 사이클이 있어서는 안된다.
플로이드-워셜 알고리즘에 대한 개념은 다음의 블로그를 참고했다.
모든 문제가 그렇듯 문제를 풀기 위해서는 입력 받은 데이터를 가공해야한다.
처음에는 인접 리스트를 구현하여 풀어보려고 했는데, 이 플로이드-워셜 알고리즘을 사용하는 문제인 것을 알게 되었고 플로이드-워셜 알고리즘의 경우는 인접 행렬로 표현하여 구현한다는 것도 알게 되었다.
그렇기 때문에 인접 행렬을 구현했다.
1
2
3
4
5
6
7
8
9
10
11
12
st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken()); // 정점의 개수
e = Integer.parseInt(st.nextToken()); // 간선의 개수
arr = new int[v + 1][v + 1];
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = arr[y][x] = 1;
}
각각 정점과 간선의 개수를 입력 받고 인접 행렬을 나타낼 배열을 초기화했다.
그 다음 반복문을 실행시켜 각 정점들 중 간선으로 연결된 정점들을 1로 표현했다.
이 때, 인접 행렬을 표현하기 위한 반복문은 간선의 개수를 기준으로 실행시켜야한다.
정점보다 간선이 많을 수 있기 때문이다.
다음으로는 정점으로 연결되지 않은 빈 공간을 무한대(INF)로 초기화해야한다.
1
2
3
4
5
6
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++) {
if (i == j) continue;
if (arr[i][j] == 0) arr[i][j] = INF;
}
}
이 빈 공간들을 무한대로 초기화하는 이유는 플로이드-워셜 알고리즘 때문이다.
이 알고리즘은 기본적으로 각 정점을 거쳐가는 경우를 고려하여 최단 거리를 업데이트한다.
다시 말해, 경로가 없는 곳과 경로가 있는 곳을 구분하기 위해서이다.
만약 경로가 없는 곳을 0으로 초기화하면, 경로가 있는 곳과 비교했을 때 항상 0이 더 작게 되므로, 경로가 없는데도 불구하고 거리가 0인 것으로 오해할 수 있다.
따라서, 경로가 없는 곳은 무한대로 초기화하여 경로가 있는 곳과 명확히 구분할 필요가 있다.
다음으로는 플로이드-워셜 알고리즘의 구현이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void floydWarshall() {
for (int k = 1; k <= v; k++) {
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++) {
if (arr[i][k] != 0 && arr[k][j] != 0) {
if (arr[i][j] == 0)
arr[i][j] = arr[i][k] + arr[k][j];
else
arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
}
}
여기서 k는 거쳐가는 정점, i와 j는 시작 정점과 도착 정점을 의미한다.
이 로직은 모든 정점 k에 대해, 모든 정점의 쌍(i, j)이 정점 k를 거쳐가는 경우를 고려하여 최단 거리를 업데이트한다.
조건인 (arr[i][k] != 0 && arr[k][j] != 0)은 정점 i에서 정점 k로 가는 경로와 정점 k에서 정점 j로 가능 경로가 모두 존재할 때를 의미한다.
이 경우에만 정점 k를 거쳐가는 경로를 고려하기 위함이다.
내부 조건인 (arr[i][j] == 0)은 정점 i에서 정점 j로 가는 직접적인 경로가 없을 때를 의미한다.
이 경우에는 정점 k를 거쳐가는 거리는 arr[i][j]에 할당한다.
마지막으로 위 조건에 해당하지 않는 나머지의 경우에는 정점 i에서 정점 j로 가는 직접적인 경로와 정점 k를 거쳐가는 경로 중 더 짧은 거리를 arr[i][j]에 할당한다.
이렇게 알고리즘이 반복되면, 결국 모든 정점에서 모든 정점으로의 최단거리를 구할 수 있게 된다.
위 과정을 거친 후, 아래와 같이 정답을 출력하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minIndex = 1; // 최소 케빈 베이컨 수를 가진 사용자의 인덱스
int minBacon = Integer.MAX_VALUE; // 최소 케빈 베이컨 수
for (int i = 1; i <= v; i++) {
int bacon = 0; // i번째 사용자의 케빈 베이컨 수
for (int j = 1; j <= v; j++) {
bacon += arr[i][j];
}
if (bacon < minBacon) {
minBacon = bacon;
minIndex = i;
}
}
System.out.println(minIndex); // 최소 케빈 베이컨 수를 가진 사용자의 인덱스
배열의 내부를 순회하여 처음부터 끝까지의 정점이 가진 케빈 베이컨을 찾아내고, 가장 적은 케빈 베이컨을 가진 정점을 리턴한다.
전체 소스코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] arr;
static int v, e, INF = 1000000;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken()); // 정점의 개수
e = Integer.parseInt(st.nextToken()); // 간선의 개수
arr = new int[v + 1][v + 1];
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[x][y] = arr[y][x] = 1;
}
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++) {
if (i == j) continue;
if (arr[i][j] == 0) arr[i][j] = INF;
}
}
floydWarshall();
int minIndex = 1; // 최소 케빈 베이컨 수를 가진 사용자의 인덱스
int minBacon = Integer.MAX_VALUE; // 최소 케빈 베이컨 수
for (int i = 1; i <= v; i++) {
int bacon = 0; // i번째 사용자의 케빈 베이컨 수
for (int j = 1; j <= v; j++) {
bacon += arr[i][j];
}
if (bacon < minBacon) {
minBacon = bacon;
minIndex = i;
}
}
System.out.println(minIndex); // 최소 케빈 베이컨 수를 가진 사용자의 인덱스
}
// 모든 쌍의 거리를 구하는 함수
public static void floydWarshall() {
for (int k = 1; k <= v; k++) {
for (int i = 1; i <= v; i++) {
for (int j = 1; j <= v; j++) {
if (arr[i][k] != 0 && arr[k][j] != 0) {
if (arr[i][j] == 0)
arr[i][j] = arr[i][k] + arr[k][j];
else
arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
}
}
}
사실 플로이드-워셜 알고리즘의 개념을 이해하기 위해 블로그를 한 곳만 본 것은 아니다.
그런데 대부분은 처음 접하는 내가 이해하기 좀 어려워서 링크를 달지 않았다.
솔직히 플로이드-워셜 알고리즘을 전부 이해하진 못한 기분이라 찝찝하다.
설명에 나왔던 다익스트라도 마찬가지라 관련 문제들을 풀어봐야할지 고민이된다.
아마 BFS/DFS 문제를 조금 더 풀고 특정 알고리즘 문제들을 좀 더 깊게 풀어보지 않을까싶다.