[Java] BOJ1197_최소 스패닝 트리

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

---

문제 제목 그대로 최소 스패닝 트리(MST)를 구하는 문제이다.

MST 알고리즘에는 대표적으로 Prim과 Kruskal 알고리즘이 있다.

Prim 알고리즘은 V^2의 시간 복잡도, Kruskal은 ElogE의 시간 복잡도를 가진다. 하지만 Prim알고리즘을 우선순위 큐를 이용하여 구현할 시 ElogV의 시간 복잡도로 이 문제에서 가장 빠르게 해결할 수 있다.

 

가중치가 가장 적은 정점이 선택 될 때 res에 가중치를 더해주었고 모든 정점이 선택되었을 때 반복문을 빠져나왔다.

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		ArrayList<int[]>[] list = new ArrayList[N];
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken())-1;
			int to = Integer.parseInt(st.nextToken())-1;
			int weight = Integer.parseInt(st.nextToken());
			list[from].add(new int[] {to, weight});
			list[to].add(new int[] {from, weight});
		}
		int res = 0;
		boolean[] visit = new boolean[N];
		PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[1] - o2[1];
			}
		});
		q.offer(new int[] {0, 0});
		int cnt = 0;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int node = temp[0];
			int weight = temp[1];
			if(visit[node]) continue;
			visit[node] = true;
			res += weight;
			if(++cnt == N) break;
			for (int[] i : list[node]) {
				if(!visit[i[0]]) {
					q.offer(new int[] {i[0], i[1]});
				}
			}
		}
		System.out.println(res);
	}

}