문제 개요 🏙️
문제에서는 주어진 도시와 도시들을 잇는 도로(간선) 정보를 바탕으로 모든 도시를 연결하면서, 두 개의 분리된 마을로 분할하는 최소 비용 계획을 수립해야 합니다.
즉, 최소 신장 트리(MST)를 구성한 뒤, MST에서 가장 비용이 큰 간선을 제거하여 두 개의 분리된 마을로 나누는 방식입니다.
접근 방법 🔍
1. Kruskal 알고리즘을 이용한 MST 구성 ✨
-
간선 정렬:
모든 간선을 가중치 오름차순으로 정렬합니다.
(자바의 경우Collections.sort()또는Arrays.sort()를 활용) -
Union-Find (Disjoint Set):
MST를 구성할 때 사이클이 발생하지 않도록 하기 위해 Union-Find 자료구조를 사용합니다.
경로 압축(Path Compression)을 적용한find()함수를 통해 효율적인 연산을 보장합니다. 🔗 -
MST 구성:
정렬된 간선들을 순회하면서 두 노드의 대표(부모)가 다른 경우에만 union 연산을 진행하며 MST에 추가합니다.
2. 두 가지 MST 구성 방식 비교 ⚖️
방식 1: 전체 MST 구성 후 최대 간선 제거 🛠️
-
구현 방법:
- 전체 MST를 구성하고, MST에 포함된 간선들 중 최대 비용 간선을 찾습니다.
- 최종 비용에서 최대 비용 간선을 빼면, 두 개의 분리된 마을로 나눌 수 있습니다.
-
코드 예시:
Collections.sort(connInfo, Comparator.comparingInt(o -> o[2])); int answer = 0; int max = 0; for (int i = 0; i < connInfo.size(); i++) { int[] cur = connInfo.get(i); int from = cur[0]; int to = cur[1]; int val = cur[2]; if (isNotSameParent(from, to)) { union(from, to); answer += val; max = Math.max(max, val); } } return answer - max;
방식 2: 조기 종료를 통한 개선 ⏩
-
아이디어:
MST 구성에 필요한 간선의 개수가 N-1개 중, 도시를 두 개의 마을로 분리하기 위해서는 N-2개의 간선만 선택하면 됩니다. -
장점:
정렬된 간선들을 순회하며, N-2개의 간선이 선택되면 즉시 반복문을 종료할 수 있어 불필요한 연산을 줄일 수 있습니다. -
코드 예시:
Collections.sort(connInfo, Comparator.comparingInt(o -> o[2])); int answer = 0; int cnt = 0; for (int i = 0; i < connInfo.size(); i++) { if (cnt == N - 2) break; int[] cur = connInfo.get(i); int from = cur[0]; int to = cur[1]; int val = cur[2]; if (isNotSameParent(from, to)) { union(from, to); answer += val; cnt++; } } return answer;
3. union() 구현 시 대소 비교에 대한 고찰 🤔
-
경로 압축이 적용된 find() 함수가 있는 경우,
union 시에 항상 작은 값(또는 rank 기반)을 부모로 설정하는 힌리스(union heuristic)를 추가하지 않아도
전체 시간복잡도는 (O(α(n)))로 거의 상수 시간에 동작합니다. -
실제 성능 면에서는 상수 오버헤드 및 메모리 접근 패턴 차이가 있을 수 있으나,
경로 압축만으로도 충분히 효율적인 연산을 보장하므로 코드의 간결함을 위해 별도 비교 없이 처리해도 무방합니다. 👍
최종 코드 정리 💻
아래는 방식 2 (조기 종료)를 적용한 최종 코드 예시입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static List<int[]> connInfo = new ArrayList<>();
private static int[] parents;
public static void main(String[] args) throws IOException {
inputSetting();
System.out.println(findAnswerByMst());
}
private static int findAnswerByMst() {
// 초기화: 각 노드의 부모는 자기 자신 👤
for (int i = 0; i < N + 1; i++) {
parents[i] = i;
}
// 간선 정보를 가중치 오름차순으로 정렬 🔢
Collections.sort(connInfo, Comparator.comparingInt(o -> o[2]));
int answer = 0;
int cnt = 0;
// MST 구성 (두 개의 마을을 만들기 위해 N-2개의 간선만 선택)
for (int i = 0; i < connInfo.size(); i++) {
if (cnt == N - 2) break;
int[] cur = connInfo.get(i);
int from = cur[0];
int to = cur[1];
int val = cur[2];
if (isNotSameParent(from, to)) {
union(from, to);
answer += val;
cnt++;
}
}
return answer;
}
private static void union(int from, int to) {
int fromParent = find(from);
int toParent = find(to);
parents[toParent] = fromParent;
}
private static boolean isNotSameParent(int from, int to) {
return find(from) != find(to);
}
private static int find(int node) {
if (parents[node] == node) return node;
return parents[node] = find(parents[node]);
}
private static void inputSetting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parents = new int[N + 1];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int val = Integer.parseInt(st.nextToken());
connInfo.add(new int[]{from, to, val});
}
}
}