문제
N개의 집과 M개의 길이 있는 마을을 두 마을로 분리할 때, 유지할 길의 비용 합을 최소화하라.
입력
첫째 줄에 N, M, 이후 M줄에 양 끝 집과 비용이 주어진다.
출력
최소 유지비 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 12 1 2 3 1 3 2 ... | 8 |
풀이
MST를 구한 뒤 가장 비용이 큰 간선 하나를 제거하여 두 마을로 분리한다.
- 프림 알고리즘으로 MST를 구성한다
- MST 간선 중 최대 가중치를 기록한다
- MST 총 비용에서 최대 가중치를 빼면 두 마을의 최소 유지비가 된다
핵심 아이디어: MST에서 가장 비싼 간선을 제거하면 두 개의 연결 컴포넌트가 되며, 이것이 최소 비용으로 마을을 분리하는 방법이다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day556BOJ1647도시분할계획 {
static class Node implements Comparable<Node> {
int idx;
int weight;
public Node(int idx, int weight) {
this.idx = idx;
this.weight = weight;
}
@Override
public int compareTo(Node e) {
return this.weight - e.weight;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int N = Integer.parseInt(inputs[0]);
int M = Integer.parseInt(inputs[1]);
ArrayList<Node>[] nodes = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
nodes[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
inputs = br.readLine().split(" ");
int a = Integer.parseInt(inputs[0]);
int b = Integer.parseInt(inputs[1]);
int w = Integer.parseInt(inputs[2]);
nodes[a].add(new Node(b, w));
nodes[b].add(new Node(a, w));
}
boolean visited[] = new boolean[N + 1];
int cnt = 0;
int result = 0;
int max_weight = 0;
PriorityQueue<Node> q = new PriorityQueue<Node>();
q.add(new Node(1, 0));
while (true) {
Node cur = q.poll();
if (visited[cur.idx])
continue;
visited[cur.idx] = true;
result += cur.weight;
max_weight = Math.max(max_weight, cur.weight);
cnt++;
if (cnt == N)
break;
for (Node v : nodes[cur.idx]) {
if (!visited[v.idx]) {
q.add(new Node(v.idx, v.weight));
}
}
}
System.out.println(result - max_weight);
}
}복잡도
- 시간: O(E log E)
- 공간: O(V + E)