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

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

1647번: 도시 분할 계획

 

크루스칼(Kruskal) 문제입니다.

https://ksb-dev.tistory.com/115 기본 크루스칼에 대해 간략하게 나마 적어놨습니다.

 

문제를 요약하면 다음과 같습니다.

각 집을 연결하는 간선이 주어졌을 때, 최소로 연결하는 간선의 합을 구하시오. 단, 두 개의 집합이 만들어져야 한다.

 

시작 정점이 없고 최소로 연결하는 간선의 합을 구하는 알고리즘은 크루스칼입니다.

여기까지는 매우 떠올리기 쉽습니다.

그렇다면 간선의 합을 최소로 하면서 어 떻게 두 개의 집합을 만들어야 할까요?

 

생각해보면 매우 간단합니다.

크루스칼은 가중치가 가장 작은 간선을 선택하면서 사이클이 발생하지 않도록 해야합니다.

따라서, 제일 마지막에 추가되는 간선이 모든 노드를 연결하면서 최소인 것이지요?

그렇다면, 제일 마지막에 추가되는 간선을 제거하면 어떻게 될까요?

제일 마지막에 추가되는 간선을 제거함으로써 두 개의 집합이 생기게 되고, 다른 모든 간선은 전체에서 최소가 됩니다.

즉, 기본 크루스칼을 구현하고 제일 마지막의 간선만 제거하면 끝납니다.

 

[구현 코드]

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static int n, m;
    private static int[] parents;
    private static PriorityQueue<House> pq;

    private static class House implements Comparable<House>{
        int s, e, w;

        House(int s ,int e, int w){
            this.s = s;
            this.e = e;
            this.w = w;
        }

        @Override
        public int compareTo(House o) {
            if(this.w > o.w){
                return 1;
            }else if(this.w < o.w){
                return -1;
            }else {
                return 0;
            }
        }
    }

    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 stz = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());

        pq = new PriorityQueue<>();
        parents = new int[n+1];

        for (int i = 0; i < n+1; i++) {
            parents[i] =i;
        }

        for (int i = 0; i < m; i++) {
            stz= new StringTokenizer(br.readLine()," ");

            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());
            int c = Integer.parseInt(stz.nextToken());

            pq.add(new House(a, b, c));
        }

        int cnt = n-1;
        int ans  = 0;
        int lastW = 0; // 제일 마지막에 추가되는 간선의 가중치

        while (cnt>0){
            House h = pq.poll();

            // 사이클이 생기지 않는다면
            if(union(h.s, h.e)){
                ans += h.w;
                cnt--;
            }

            if(cnt == 0) lastW = h.w; // 마지막 가중치 저장
        }

        // 마지막 가중치 제거 후 출력
        bw.write(String.valueOf(ans - lastW));

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean union(int a, int b){
        int root1 = find(a);
        int root2 = find(b);

        if(root1 == root2) return false;

        if(root1 < root2){
            parents[root1] = root2;
        }else{
            parents[root2] = root1;
        }
        return true;
    }

    private static int find(int a){
        if(parents[a] == a){
            return a;
        }
        return find(parents[a]);
    }
}