[백준] 1197. 최소 스패닝 트리 (Java)

 

🔒 문제

1197번: 최소 스패닝 트리

 

🔑 알고리즘

최소 스패닝 트리(MST), 크루스칼 알고리즘(Kruskal)

 

💡  풀이

최소 스패닝 트리를 찾는 알고리즘으로 크루스칼과 프림 알고리즘이 유명하다.

크루스칼 알고리즘은 그리디하게 가장 가중치가 낮은 간선들부터 연결하는 방법으로 간선을 정렬해야하기 때문에 O(ElogE)의 시간 복잡도를 갖는다.

해당 문제는 간선 10,000, 정점이 100,000인 희소그래프이기 때문에

O(V²) 의 시간 복잡도를 갖는다고 하는 프림 알고리즘보다 크루스칼 알고리즘이 효율적이라고 생각하였다.

 

* 우선순위 큐는 순회할 경우 정렬을 보장하지 않는다고 한다. poll()을 사용해야한다.

 

 

✏️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int V, E, parent[];
	static PriorityQueue<Edge> pq;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		parent = new int[V + 1];
		for (int i = 1; i <= V; i++)
			parent[i] = i;

		pq = new PriorityQueue<>();
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			pq.add(new Edge(a, b, w));
		}

		System.out.println(kruskal());
	}

	private static int kruskal() {
		int sum = 0;
		int count = 0;
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			
			// 사이클을 만들지 않는다면 채택
			if (union(edge.from, edge.to)) {
				sum += edge.w;
				if (++count == V - 1)
					return sum;
			}
		}
		return sum;
	}

	// 루트가 동일하지 않다면 (사이클을 만들지 않는다면) 합치기
	private static boolean union(int a, int b) {
		a = find(a);
		b = find(b);

		if (a == b)
			return false;
		parent[a] = b;
		return true;
	}

	// 루트 탐색
	private static int find(int a) {
		if (a == parent[a])
			return a;
		return parent[a] = find(parent[a]);
	}

	static class Edge implements Comparable<Edge> {
		int from, to, w;

		public Edge(int from, int to, int w) {
			this.from = from;
			this.to = to;
			this.w = w;
		}

		@Override
		public int compareTo(Edge o) {
			return w - o.w;
		}
	}
}