[백준 1647번/JAVA] 도시 분할 계획

문제

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

풀이

MST를 하나 만든 다음, 가중치가 제일 큰 길 하나를 끊으면 된다.
kruskal로 MST 만드는 방법
문제 조건에 따르면 마을에 집이 하나 이상만 있으면 된다고 했으므로,
Kruskal 알고리즘으로 가중치가 작은 길부터 순서대로 선택한 다음 가장 마지막 길을 끊으면
가중치가 가장 큰 길을 없앰으로써 N-1, 1개로 마을이 나뉘어지고 비용이 가장 적게 들게 된다.

코드

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

public class Main {
    static List<Node> list = new ArrayList<>();
    static int[] parent;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int sum = 0;
        int lastCost = 0;

        st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        parent = new int[V+1]; //부모 노드 저장
        for(int i=0; i<V+1; 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());
            Node node = new Node(A, B, C);
            list.add(node);
        }
        Collections.sort(list); //비용 기준 오름차순 정렬

        for(int i=0; i<list.size(); i++){
            Node node = list.get(i);
            if(!isSameParent(node.x, node.y)){
                union(node.x, node.y);
                sum += node.z;
                lastCost = node.z; //가장 마지막에 선택된 비용
            }
        }
        sum = sum - lastCost; //lastCost를 전체 비용에서 제외
        bw.write(sum+" ");
        bw.close();
    }

    static boolean isSameParent(int x, int y){
        //부모노드 찾기
        x = find(x);
        y = find(y);
        if(x != y)
            return false;
        return true;
    }
    static int find(int x){
        if(parent[x] == 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;
        else if(x > y) parent[x] = y;
    }
}
class Node implements Comparable<Node>{
    int x, y, z;

    Node(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public int compareTo(Node n){
        return this.z - n.z; 
    }
}