원더랜드(최소 스패닝 트리 : 크루스칼 , Union & Find 활용)
문제
설명
원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다.
원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다.
아래의 그림은 그 한 예를 설명하는 그림이다.
위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다.
입력
첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다.
다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.
이는 A번 도시와 B번 도시가 유지비용이 C인 도로로 연결되어 있다는 의미이다.
출력
모든 도시를 연결하면서 드는 최소비용을 출려한다.
예시 입력 1
9 12
1 2 12
1 9 25
2 3 10
2 8 17
2 9 8
3 4 18
3 7 55
4 5 44
5 6 60
5 7 38
7 8 35
8 9 15
예시 출력 1
196
해결방법
- 비용 기준으로 오름차순 정렬된 간선 배열을 순서대로 읽어들여, 같은 집합에 속하는 간선인지 판단
- 같은 집합이 아니다 → 같은 집합 처리 후 해당 간선을 선택!
- 같은 집합이면 스킵 한다.(스패닝 트리는 회로가 되면 안된다.)
- 어차피 연결되어 있는 정점 인데, 또 선택하면 비용낭비.
코드
import java.util.*;
class Edge implements Comparable<Edge> {
public int v1;
public int v2;
public int cost;
Edge(int v1, int v2, int cost) {
this.v1 = v1;
this.v2 = v2;
this.cost = cost;
}
@Override
public int compareTo(Edge ob) {
return this.cost - ob.cost;
}
}
class Main {
static int[] unf;
public static int Find(int v) {
if (v == unf[v]) return v;
else return unf[v] = Find(unf[v]);
}
public static void Union(int a, int b) {
int fa = Find(a);
int fb = Find(b);
if (fa != fb) unf[fa] = fb;
}
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
unf = new int[n + 1];
ArrayList<Edge> arr = new ArrayList<>();
// 집합 초기화.
for (int i = 1; i <= n; i++) unf[i] = i;
// 입력 값 입력.
for (int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
int c = kb.nextInt();
// 배열 객체에 정점 정보 입력.
arr.add(new Edge(a, b, c));
}
int answer = 0;
// 비용 낮은 순서대로 정렬
Collections.sort(arr);
// 집합 정의 처리.
for (Edge ob : arr) {
int fv1 = Find(ob.v1);
int fv2 = Find(ob.v2);
// 서로 다른 집합인 정점에 대한 연결 비용을 정답에 누적.
if (fv1 != fv2) {
answer += ob.cost;
Union(ob.v1, ob.v2);
}
// 트리의 조건 중 하나가 완성된 트리의 간선 개수는 정점 개수 - 1 이기 때문에
// 이를 체크하는 로직을 두어도 된다. 그러나 보통 문제는 그렇게 안주기 떄문에 굳이 안해도 됨.
}
System.out.println(answer);
}
}
