[Algorithm] 🌴백준 1197 최소 스패닝 트리

0. 문제

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

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

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

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

1. 아이디어

Kruskal Algorithm 이용
💡 PriorityQueue 이용하여 가장 작은 가중치부터 연결함
💡 사이클을 생기지 않게 하려고, Union & Find 이용하여 Disjoint set 구현

2. 핵심 풀이

1) PriorityQueue 이용하여 가장 작은 가중치부터 연결함

pq.offer(new Edge(start,end,cost));
...
while(!pq.isEmpty()) {
	Edge e = pq.poll();
			
	if(find(e.start) == find(e.end)) 
    	continue;
	else {
		union(e.start, e.end);
		count+=e.cost;
	}
}

2) find함수를 통해 서로의 root가 같은지 확인(사이클 없애기 위해)

static int find(int e) {
	if(parent[e] == e) return e;
	return parent[e] = find(parent[e]);
}

3) union함수를 통해 서로를 트리로 연결함

static void union(int a, int b) {
	int rootA = find(a);
	int rootB = find(b);
		
	if(rootA != rootB) 
    	parent[rootB] = rootA;
}

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class MST_1 {
	static int[] parent;
	static PriorityQueue<Edge> pq;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s[] = br.readLine().split(" ");
		
		int count = 0;
		int V = Integer.parseInt(s[0]);
		int E = Integer.parseInt(s[1]);
		parent = new int[V+1];
		pq = new PriorityQueue<Edge>();
		
		for(int i=0; i<V+1; i++)
			parent[i] = i;
		
		for(int i=0; i<E; i++) {
			s = br.readLine().split(" ");
			int start = Integer.parseInt(s[0]);
			int end = Integer.parseInt(s[1]);
			int cost = Integer.parseInt(s[2]);
			pq.offer(new Edge(start,end,cost));
		}
		
		while(!pq.isEmpty()) {
			Edge e = pq.poll();
			
			if(find(e.start) == find(e.end)) continue;
			else {
				union(e.start, e.end);
				count+=e.cost;
			}
		}
		
		System.out.println(count);
	}
	
	static int find(int e) {
		if(parent[e] == e) return e;
		return parent[e] = find(parent[e]);
	}
	
	static void union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		
		if(rootA != rootB) parent[rootB] = rootA;
	}

	static class Edge implements Comparable<Edge>{
		int start;
		int end;
		int cost;
		
		Edge(int start, int end, int cost){
			this.start = start;
			this.end = end;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}
	}
}

4. 결과

성공✨