[백준] 1647번 '도시 분할 계획' - Java

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

---

문제

---

코드

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

public class Main {
	public static class Node implements Comparable<Node>{
		int s;
		int e;
		int cost;
		
		public Node(int s, int e, int cost) {
			this.s = s;
			this.e = e;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Node n1) {
			return this.cost - n1.cost;
		}
	}
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int n, m;
	private static PriorityQueue<Node> q;
	private static int[] parent;
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		q = new PriorityQueue<>();
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(bf.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			q.offer(new Node(s, e, cost));
		}
		
		parent = new int[n + 1];
		bw.write(kruscal() + "\n");
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	public static int kruscal() {
		for(int i = 1 ; i <= n ; i++) {
			parent[i] = i;
		}
		
		int count = 0;
		int dist = 0;
		while(count < n - 2) {
			Node node = q.poll();
			int p1 = find(node.s);
			int p2 = find(node.e);
			
			if(p1 != p2) {
				union(p1, p2);
				dist += node.cost;
				count ++;
			}
		}
		return dist;
	}
	
	public static void union(int a, int b) {
		parent[a] = b;
	}
	
	public static int find(int a) {
		if(parent[a] == a) return a;
		else return parent[a] = find(parent[a]);
	}
}

설명은.. 내일 쓸게요.. 이 모든 건 이 썩어빠진 세상 때문입니다........

---

Search

https://moonsbeen.tistory.com/145