BOJ 1414 불우이웃돕기
https://www.acmicpc.net/problem/1414
문제
다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다.
다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때, A와 B가 서로 랜선으로 연결되어 있거나, 또 다른 컴퓨터를 통해서 연결이 되어있으면 서로 통신을 할 수 있다.
다솜이는 집 안에 있는 N개의 컴퓨터를 모두 서로 연결되게 하고 싶다.
N개의 컴퓨터가 서로 연결되어 있는 랜선의 길이가 주어질 때, 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선의 길이를 의미한다. 랜선의 길이는 a부터 z는 1부터 26을 나타내고, A부터 Z는 27부터 52를 나타낸다. N은 50보다 작거나 같은 자연수이다.
출력
첫째 줄에 다솜이가 기부할 수 있는 랜선의 길이의 최댓값을 출력한다. 만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.
예제 입력 1
3 abc def ghi
예제 출력 1
40
예제 입력 2
2 a0 0b
예제 출력 2
-1
코드
오랜만에 푼 최소 스패닝 트리 문제였다.
문제의 출력 조건에 다음과 같이 명시되어 있다.
만약, 모든 컴퓨터가 연결되어 있지 않으면 -1을 출력한다.
처음 문제를 풀 때, 생각 없이 부모 인덱스를 저장한 배열을 순회하며 전부 같은 부모 인덱스를 가리키고 있지 않으면 -1을 출력하게 했다.
하지만, 마지막으로 노드가 추가되는 union 과정에서 추가되는 노드의 부모 인덱스가 다른 노드들의 부모 인덱스로 초기화되지 않을 수 있다.
union 메소드의 동작을 잘 확인해보고, 이해가 가지 않으면 크루스칼 알고리즘 동작 과정 예시를 검색해서 살펴보도록 하자.
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
static class Edge {
int node1;
int node2;
int weight;
public Edge(int node1, int node2, int weight) {
this.node1 = node1;
this.node2 = node2;
this.weight = weight;
}
}
static int N;
static int[] parents;
// 랜선의 길이가 짧은 것을 우선시하는 우선순위 큐
static PriorityQueue<Edge> edges = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int length = charToInt(br.read());
// i와 j 사이에 랜선이 존재하면, 우선순위 큐에 추가
if(length != 0) {
edges.offer(new Edge(i, j, length));
}
}
br.readLine();
}
// 부모 인덱스 초기화
parents = new int[N];
for (int i = 1; i < N; i++) {
parents[i] = i;
}
int toDonate = kruskal();
System.out.println(toDonate);
}
/**
* 문자로 표현된 랜선의 길이를 정수로 변환해주는 메소드
* @param input 문자로 표현된 랜선의 길이
* @return 정수로 변환된 랜선의 길이
*/
static int charToInt(int input) {
if(input >= 'a') {
return input - 'a' + 1;
}
if(input >= 'A') {
return input - 'A' + 27;
}
return 0;
}
static int kruskal() {
int totalLength = 0; // 기부할 수 있는 랜선의 길이의 총합
int usedCable = 0; // 사용된 랜선의 수
while (!edges.isEmpty()) {
Edge edge = edges.poll();
int parent1 = find(edge.node1);
int parent2 = find(edge.node2);
// 연결되지 않은 컴퓨터일 경우, 해당 랜선을 사용한다.
if(parent1 != parent2) {
usedCable++;
union(edge.node1, edge.node2);
}
// 이미 기존에 연결된 컴퓨터일 경우, 해당 랜선을 기부할 랜선에 추가시킨다.
else {
totalLength += edge.weight;
}
}
// 올바른 최소 스패닝 트리는 노드가 N개일 때, 간선이 N-1개여야 한다.
// 사용된 랜선이 N-1개가 아니라는 것은
// 문제에서 요구하는 올바른 네트워크가 형성되지 않은 것이기 때문에, -1을 반환한다.
if(usedCable != N - 1) {
return -1;
}
return totalLength;
}
static void union(int node1, int node2) {
int parent1 = find(node1);
int parent2 = find(node2);
if(parent1 < parent2) {
parents[parent2] = parent1;
} else {
parents[parent1] = parent2;
}
}
static int find(int node) {
if(parents[node] == node) {
return node;
}
return parents[node] = find(parents[node]);
}
}