[백준] 최소 스패닝 트리 (JAVA)

🎄 최소 스패닝 트리

 

MST(Minimal Spanning Tree)의 기본이 되는 문제이다.

프로그래머스에 "섬 연결하기" 라는 문제가 있는데, 거의 똑같다.

따라서 위 문제에 대한 풀이를 참고하여 해결할 수 있다.  

 

---

문제

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

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

 

입력

첫째 줄에 정점의 개수 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.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Edge implements Comparable<Edge> {
	int v1;
	int v2;
	int cost;

	Edge(int v1, int v2, int cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge edge) {
		return this.cost - edge.cost;
	}
}

class Main {
	static int V;
	static int E;
	static int[] parent;
	static PriorityQueue<Edge> pq = new PriorityQueue<>();

	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()) + 1;
		E = Integer.parseInt(st.nextToken());
		parent = new int[V];

		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			pq.add(new Edge(v1,v2,cost));
		}

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

	private static int kruskal() {
		for(int i=1; i<V; i++) {
			parent[i] = i;
		}

		int sum = 0;
		while(!pq.isEmpty()) {
			Edge edge = pq.poll();
			int v1 = edge.v1;
			int v2 = edge.v2;
			int cost = edge.cost;

			int v1Parent = findParent(v1);
			int v2Parent = findParent(v2);

			if(v1Parent == v2Parent) continue;

			sum += cost;
			if(v1Parent < v2Parent)
				parent[v2Parent] = v1Parent;
			else parent[v1Parent] = v2Parent;
		}
		return sum;
	}

	private static int findParent(int node) {
		if(parent[node] == node) return node;
		return parent[node] = findParent(parent[node]);
	}
}

 

 

---

 

1197번: 최소 스패닝 트리