[Java] 백준 1197번 : 최소 스패닝 트리

문제

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

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

입력

첫째 줄에 정점의 개수 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

3 3
1 2 1
2 3 2
1 3 3

예제 출력 1

3

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;

	private static int V, E;
	private static List<Node> list;
	private static int[] parent;

	static class Node implements Comparable<Node> {
		int r, c, weight;

		public Node(int r, int c, int weight) {
			super();
			this.r = r;
			this.c = c;
			this.weight = weight;
		}

		@Override
		public String toString() {
			return "Node [r=" + r + ", c=" + c + ", weight=" + weight + "]";
		}

		@Override
		public int compareTo(Node o) {
			return this.weight-o.weight;
		}
	}

	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		V=Integer.parseInt(st.nextToken());
		E=Integer.parseInt(st.nextToken());
		list=new ArrayList<>();
		parent=new int[V+1];
		for(int i=1;i<=V;i++) parent[i]=i;
		
		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());
			list.add(new Node(a, b, w));
		}
		Collections.sort(list);
		
		int answer=0;
		for(int i=0;i<list.size();i++) {
			int a=list.get(i).r;
			int b=list.get(i).c;
			int weight=list.get(i).weight;
			if(findParent(a)!=findParent(b)) {
				answer+=weight;
				union(a, b);
			}
		}
		
		System.out.println(answer);
	}

	private static int findParent(int x) {
		if(x==parent[x]) return x;
		return parent[x]=findParent(parent[x]);
	}
	
	private static void union(int a, int b) {
		int A=findParent(a);
		int B=findParent(b);
		if(A==B) return;
		parent[A]=b; 
	}
}

Union Find로 크루스칼 알고리즘을 이용하여 해결하였습니다.