[Algorithm] 백준 1197 최소스패닝트리 - union-find, 크루스칼 알고리즘

문제

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

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

입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

---

풀이

• 사이클 없이 모든 노드를 방문해야 하므로 크루스칼 알고리즘을 이용해 union-find 자료구조를 사용한다
• 크루스칼 알고리즘의 기본은 간선을 기준으로 생각하는 것이므로 간선 클래스를 만든다
• 가중치가 작은 순서대로 사용해야하므로 클래스 정렬기준을 만들어 우선순위큐를 사용해 오름차순으로 꺼낸다

public class BOJ1197 {
	
	// 간선 클래스, 우선순위큐를 사용하기 위한 정렬 기준을 가진다.
	static class Edge implements Comparable<Edge>{
		int from, to, dist;
		public Edge(int from, int to, int dist) {
			this.from = from;
			this.to = to;
			this.dist = dist;
		}
		
		@Override
		public int compareTo(Edge n1) {
			return Integer.compare(dist, n1.dist);
		}
	}

	static int V, E, ans=0;
	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] arr = br.readLine().split(" ");
		V = Integer.parseInt(arr[0]);
		E = Integer.parseInt(arr[1]);
		parent = new int[V+1];
		
		// 부모노드 초기화
		for(int i=1; i<=V; i++) parent[i] = i;
		
		PriorityQueue<Edge> queue = new PriorityQueue<Edge>();
		for(int i=0; i<E; i++) {
			arr = br.readLine().split(" ");
			Edge node = new Edge(Integer.parseInt(arr[0]), Integer.parseInt(arr[1]), 
					Integer.parseInt(arr[2]));
			queue.offer(node);
		}
		
		for(int i=0; i<E; i++) {
			Edge edge = queue.poll();
			
			int s = find(edge.from);
			int e = find(edge.to);
			// 시작 노드와 종료 노드의 루트가 겹치면 사이클이 생기는 것이므로 continue를 한다.
			if(s==e) continue;
			
			union(s, e);
			ans += edge.dist;
		}
		System.out.print(ans);
		
	}
	
	static int find(int a) {
		// 루트 노드는 부모 노드 번호로 자기 자신을 가진다.
		if(a==parent[a]) return a;
		// 각 노드의 부모를 찾아 올라간다.
		else parent[a] = find(parent[a]);
		return parent[a];
	}
	
	static void union(int a, int b) {
		// 각 원소가 속한 트리의 루트노드를 찾는다.
		int rootA = find(a);
		int rootB = find(b);
		// 루트가 동일하지 않다면 a의 루트노드를 b로 지정하여 두 트리를 합친다.
		if(rootA!=rootB) parent[rootA] = b;
		// 같은 트리에 속할 경우 함수를 종료한다.
		else return;
	}
}