[Java] 백준(실버-1) 1389번 - 케빈 베이컨의 6단계 법칙
문제 풀이
이 문제는 플로이드 워셜 알고리즘을 이용해 풀 수 있는 문제이다.
아이디어 도출
이전에 풀어봤던 문제에서는 정점사이의 경로 여부만 체크했다면, 이번 문제에서는 모든 정점 사이의 최단거리를 구해주어야 한다.
이전에 풀었던 경로 찾기 문제에서의 조건은 단순히 거쳐가는 정점의 경로가 존재하는지 체크하는 것이었지만, 이번에는 최단 경로를 나타내야하기 때문에 arr[i][j] > arr[i][k] + arr[k][j] 일 경우, arr[i][j] = arr[j][k] + arr[k][j]로 초기화해야 한다.
이를 고려하여 문제 풀이를 위한 아이디어를 생각해보자.
- 먼저, 2차원 배열의 모든 값을 5001로 초기화한 뒤, i와 j과 같은 위치인 (1, 1), (2, 2), … (i, i)인 값은 모두 0으로 초기화 해준다.
플로이드 워셜 알고리즘은 i번째 정점에서 j번째 정점이 연결되어있지 않을 경우 무한대를 나타내는 값을 넣어줘야 하는데, 이 때, 필자는 M의 최대 범위인 5001를 넣어줬다.
- 문제에서 입력으로 주어지는 간선을 양방향으로 1로 초기화 해준다.
- 플로이드 워셜 알고리즘을 수행하여, 모든 정점에서 모든 정점 사이의 최단 거리가 담긴 arr 배열을 탐색하며 최솟값이 되는 케빈 베이컨 수를 찾으면 된다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
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
70
71
72
73
74
75
76
77
78
79
80
81
82
import java.io.*;
import java.util.*;
class Main {
// 입력 배열
static int[][] arr;
static int N, M;
static int result;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N+1][N+1];
// 배열 초기화
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
if(i == j) {
arr[i][j] = 0;
continue;
}
// i와 j가 연결되어 있지 않다면, 최대 수인 5001을 삽입한다.
arr[i][j] = 5001;
}
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
// 양방향 그래프이기에, 양방향 모두 1로 초기화한다.
arr[A][B] = 1;
arr[B][A] = 1;
}
/**
* 플로이드 워셜 알고리즘을 이용해 최단경로를 갱신한다.
* k: 거쳐가는 노드
* i: 출발 노드
* j: 도착 노드
*/
for(int k=1; k<=N; k++) {
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);
}
}
}
result = 0;
int min = Integer.MAX_VALUE;
// 가장 작은 케빈 베이컨 수를 찾는다.
for(int i=1; i<=N; i++) {
int baconNumber = 0;
for(int j=1; j<=N; j++) {
baconNumber += arr[i][j];
}
if(min > baconNumber) {
result = i;
min = baconNumber;
}
}
bw.write(result+"\n");
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.