[백준] 1647 도시 분할 계획 [자바]

 

 

---

https://steady-coding.tistory.com/116

[BOJ] 백준 1647번 : 도시 분할 계획 (JAVA)

https://moonsbeen.tistory.com/145

[백준]1647: 도시 분할 계획 - JAVA

 

 

---

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

class Node implements Comparable<Node> {
	int start;
	int end;
	int weight;
	
	public Node(int start, int end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	
	public int compareTo(Node n) {
		return this.weight - n.weight;
	}
}

public class Main {
	static int parent[];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<Node> list = new ArrayList<>();
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list.add(new Node(s,e,w));
		}
		
		Collections.sort(list);
		parent = new int[N+1];
		for(int i = 1; i<= N; i++) {
			parent[i] = i;
		}
		int sum = 0;
		int bigcost = 0;
		for(int i = 0; i < M; i++) {
			Node node = list.get(i);
			
			if(find(node.start) != find(node.end)) {
				sum += node.weight;
				union(node.start, node.end);
				
				bigcost = node.weight;
			}
		}
		System.out.println(sum - bigcost);
	}
	static int find(int x) {
		if(x == parent[x]) {
			return x;
		}
		return parent[x] = find(parent[x]);
	}
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x != y) {
			parent[y] = x;
		}
	}
}