[JAVA/백준] 1922번: 네트워크 연결

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
75
76
77
78
79
import java.util.*;
import java.io.*;
/**
 * @author HEESOO
 *
 */
/*
 * MST?
 * int[] parent, 초기화
 * Node 클래스 생성하고, 우선순위 큐에 다 넣어
 * 부모가 같으면 패스, 다르면 union하고 sum+=weight*/

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;
		
		int n=Integer.parseInt(br.readLine());
		int m=Integer.parseInt(br.readLine());
		pq=new PriorityQueue<>();
		parent=new int[n+1];
		for(int i=1;i<=n;i++) parent[i]=i; // 부모는 자기 자신
		
		for(int i=0;i<m;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();
			int parentS=find(node.start);
			int parentE=find(node.end);
			if(parentS==parentE) continue; // 둘이 연결되어 있는 경우이므로 패스
			union(parentS, parentE); // 둘을 연결 짓기
			sum+=node.weight; // 최소비용 추가
		}
		
		return sum;
	}
	
	public static int find(int x) { // x의 최상위 부모 리턴
		if(x==parent[x]) return x;
		else return parent[x]=find(parent[x]);
	}
	
	public static void union(int a, int b) { // a, 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;
	}
}