[백준/Java] 1197 최소 스패닝 트리 : 최소 신장 트리

문제

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

---

import java.util.*;

public class Main {
    private static int uf[];	// 유니온 파인드 배열
	private static PriorityQueue<pEdge> queue;
	
	public static void main(String[] args) {	
		// 최소 신장 트리(방향 X): 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
		// - 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
		// - N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개
		
		Scanner sc = new Scanner(System.in);
		
		int V = sc.nextInt();	// 노드 개수
		int E = sc.nextInt();	// 에지 개수
		queue = new PriorityQueue<>();	// 자동 정렬을 위해 우선 순위 큐 자료구조 선택
		uf = new int[V + 1];
		
		for (int i = 0; i < V; i++) {	// 유니온 파인드 배열 각 인덱스 값과 동일한 값으로 초기화(사이클 확인 용도)
			uf[i] = i;
		}
		
		for (int i = 0; i < E; i++) {
			int a = sc.nextInt();	// 노드1
			int b = sc.nextInt();	// 노드2
			int w = sc.nextInt();	// 가중치
			queue.add(new pEdge(a, b, w)); // 그래프 에지 리스트에 추가
		}
		
		int useEdge = 0;	// 사용한 에지 개수
		int result = 0;
		
		while (useEdge < V - 1) {
			pEdge now = queue.poll();
			if (find(now.a) != find(now.b)) {
				union(now.a, now.b);
				result = result + now.w;	// 가중치 더함
				useEdge++;	// 유니온 했으니까 에지 개수 증가
			}
		}
		
		System.out.println(result);
	}
	
	public static void union(int n1, int n2) {	// 대표 노드끼리 연결
		n1 = find(n1);
		n2 = find(n2);
		
		if (n1 != n2) {
			uf[n2] = n1;
		}
	}
	
	public static int find(int n) {
		if (uf[n] == n) {
			return n;
		} else {
			return uf[n] = find(uf[n]);		// 재귀 함수, 경로 압축 부분
		}
	}
}

class pEdge implements Comparable<pEdge> {
	int a, b, w;
	pEdge(int a, int b, int w) {
		this.a = a;
		this.b = b;
		this.w = w;
	}
	
	@Override
	public int compareTo(pEdge o) {
		// 가중치를 기준으로 오름차순 정렬을 하기 위해 compareTo 재정의
		return this.w - o.w;
	}
}