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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
class Main {
	static PriorityQueue<Node> pq;
	static int[] parent;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		pq=new PriorityQueue<>();
		int v=Integer.parseInt(st.nextToken());
		int e=Integer.parseInt(st.nextToken());
		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 c=Integer.parseInt(st.nextToken());
			pq.offer(new Node(a, b, c)); // 큐에 다 넣기
		}
		
		System.out.println(solve());
	}
	
	public static int solve() {
		int sum=0; // 가중치 누적 합 계산
		
		while(!pq.isEmpty()) {
			Node node=pq.poll();
			// start, end의 부모 찾기
			int parentS=find(node.start);
			int parentE=find(node.end);
			// 부모가 다르다면(연결되어있지 않다면)
			if(parentS!=parentE) {
				union(parentS, parentE); // 둘을 연결
				sum+=node.weight; // 가중치 계산
			}
		}
		
		return sum;
	}
	
	public static int find(int x) {
		if(parent[x]==x) return x;
		else return parent[x]=find(parent[x]);
	}
	
	public static void union(int a, int b) {
		parent[a]=b;
	}
}

class Node implements Comparable<Node>{
	int start;
	int end;
	int weight;
	
	public Node(int s, int e, int w) {
		this.start=s;
		this.end=e;
		this.weight=w;
	}
	
	@Override
	public int compareTo(Node n) { // 가중치 기준 오름차순 정렬
		return this.weight-n.weight;
	}
}