섹션 9 Greedy - 7. 원더랜드(최소스패닝트리 - 크루스칼 : Union&Find 이용)

문제 설명

원더랜드는 재정 부족으로 도로 유지비를 줄이려고 한다.
모든 도시를 서로 연결하면서, 유지비용이 최소가 되도록 일부 도로만 남기고 나머지는 폐쇄하려 한다.

단, 어떤 도시든 다른 도시로 갈 수 있어야 한다 (모든 도시 연결 필요)

---

입력 & 출력

입력 예시

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

 

출력 예시

196

---

해결 전략: 크루스칼 알고리즘

• MST(Minimum Spanning Tree)를 만드는 대표적인 방법 중 하나
• 모든 간선을 비용 기준으로 정렬
• 비용이 낮은 간선부터 차례대로 선택하되 이미 연결된 두 정점을 다시 연결하지는 않음 (사이클 방지)
• 이 과정을 통해 최소 비용으로 전체 연결 가능

---

전체 코드

import java.util.*;

class Edge implements Comparable<Edge> {
	public int v1, v2, 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;
	}
}

public 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 sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		unf = new int[n + 1];
		for (int i = 1; i <= n; i++) unf[i] = i;

		ArrayList<Edge> arr = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			arr.add(new Edge(a, b, c));
		}

		Collections.sort(arr);
		int answer = 0;
		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);
			}
		}
		System.out.println(answer);
		sc.close();
	}
}

---

코드 설명

• Edge: 간선 정보를 담는 클래스 (v1, v2, cost)
• compareTo: cost 기준 오름차순 정렬을 위한 오버라이딩
• int[] unf: Union-Find용 부모 배열
• Find(int v)
  • 노드 v의 대표(루트)를 반환
  • 경로 압축 적용
• Union(int a, int b)
  • 두 정점의 대표가 다르면 병합
• main()
  • n: 도시 수, m: 도로 수
  • arr: 간선 목록 저장
  • 간선 리스트 정렬 → 작은 비용부터 탐색
  • 사이클을 만들지 않으면 간선 선택 (answer += cost)

---

시간 복잡도

• 간선 정렬 : O(E log E)
• Union-Find 연산 : 거의 O(1)
• 전체 : O(E log E)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런