문제
N개의 컴퓨터를 모두 연결하는 데 필요한 최소 비용을 구하라. M개의 연결 가능한 간선과 비용이 주어진다.
입력
첫째 줄에 컴퓨터 수 N, 둘째 줄에 간선 수 M, 이후 M줄에 (노드, 노드, 비용)이 주어진다.
출력
모든 컴퓨터를 연결하는 최소 비용을 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 9 1 2 5 1 3 4 2 3 2 2 4 7 3 4 6 3 5 11 4 5 3 4 6 8 5 6 8 | 23 |
풀이
크루스칼 알고리즘으로 간선을 비용순 정렬 후, Union-Find로 사이클 없이 간선을 선택한다.
- 모든 간선을 비용 오름차순으로 정렬한다
- Union-Find 배열을 초기화한다
- 간선을 순서대로 탐색하며, 두 노드가 다른 집합이면 연결하고 비용을 누적한다
- 경로 압축을 적용한 find 연산으로 효율적으로 집합을 관리한다
핵심 아이디어: 크루스칼 알고리즘은 가장 저렴한 간선부터 선택하되 사이클이 생기지 않는 것만 추가하여 MST를 구성한다.
코드
package day449;
import java.io.*;
import java.util.*;
public class Day418BOJ1922네트워크연결 {
static int N, M, ans = 0;
static int[] p;
static ArrayList<Net> arr = new ArrayList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
StringTokenizer st;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr.add(new Net(a, b, c));
}
p = new int[N + 1];
for (int i = 1; i <= N; i++) {
p[i] = i;
}
Collections.sort(arr);
for (Net network : arr) {
if (find(network.cur) != find(network.next)) {
ans += network.cost;
union(network.cur, network.next);
}
}
System.out.println(ans);
}
static int find(int x) {
if (x == p[x]) {
return x;
}
return p[x] = find(p[x]);
}
static void union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
p[b] = a;
}
}
static class Net implements Comparable<Net> {
int cur;
int next;
int cost;
Net(int current, int next, int cost) {
this.cur = current;
this.next = next;
this.cost = cost;
}
@Override
public int compareTo(Net o) {
return this.cost - o.cost;
}
}
}복잡도
- 시간: O(E log E)
- 공간: O(V + E)