[백준 1647] 도시 분할 계획(Java)

문제 링크 : https://www.acmicpc.net/problem/1647

이 문제는 최소 스패닝 트리를 이용하여 풀 수 있습니다. 마을을 두 개로 나누고 최소의 길을 유지하기 위해서는 다음의 과정을 거칩니다.

1. 마을 전체를 최소의 길을 유지한 상태로 길을 제거한다
2. 그 중에서 가장 코스트가 큰 하나의 길만을 제거한다

이 과정을 통해 최소의 길을 가진 마을 두 개로 나눌 수 있습니다. 1번 과정의 경우 최소 스패닝 트리를 구하면 해결할 수 있고, 2번의 경우 최소 스패닝 트리 특성 상 가장 마지막에 추가되는 노드가 가중치가 가장 큰 노드이기 때문에 가장 마지막 가중치를 최소 스패닝 트리의 총 간선 합에서 빼주면 됩니다.

다음은 코드입니다.

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

class Main{
    static int N,M;
    static int[] parent;
    static PriorityQueue<Node> queue = new PriorityQueue<>();

    public static void main(String[] args) throws Exception{
        init();

        int useNum = 0;
        int result = 0;
        int maxCost = 0;
        while(useNum < N-1){
            Node curr = queue.poll();

            if(find(curr.s) != find(curr.f)){
                union(curr.s, curr.f);
                result += curr.w;
                useNum++;
                maxCost = curr.w;
            }
        }
        System.out.println(result-maxCost);
    }

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b) parent[b] = a;
    }

    static int find(int a){
        if(a != parent[a]) return parent[a] = find(parent[a]);
        else return parent[a];
    }

    static void init() throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        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());
            queue.add(new Node(a,b,c));
        }
    }

    static class Node implements Comparable<Node>{
        int s;
        int f;
        int w;

        Node(int s, int f, int w){
            this.s = s;
            this.f = f;
            this.w = w;
        }

        @Override
        public int compareTo(Node o){
            return this.w - o.w;
        }
    }
}