[백준/Java] 1647 : 도시 분할 계획

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

 

이번 문제로 MST 알고리즘입니다. 다만 MST에서 살짝 변형을 준 문제라고 생각해도 될 것 같습니다.

 

MST인 경우에는 모든 집을 연결하는 최소한의 간선 합을 구하는 것인데 여기서는 집을 두 개의 집단으로 나눠야 하기 때문에 최소한의 간선들 중 제일 큰 값을 빼면 됩니다. 그러면 A구역 B구역으로 자연스럽게 나누어질 것 입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Backjoon_1647_도시_분할_계획  {
    public static class Node implements Comparable<Node>{
        int idx1, idx2, cost;

        public Node(int idx1, int idx2, int cost) {
            this.idx1 = idx1;
            this.idx2 = idx2;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node n){
            return this.cost - n.cost;
        }

    }
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parent = new int[N+1];
        PriorityQueue<Node> pq = new PriorityQueue<>();

        Arrays.fill(parent, -1);

        for(int i = 0 ; i < M ; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            pq.offer(new Node(v1,v2,cost));
        }

        int answer = 0;
        int max = 0;
        int count = 0;
        int size = pq.size();

        for(int i = 0 ; i < size ; i++){
            Node node = pq.poll();
            if(union(node.idx1, node.idx2)){
                answer += node.cost;
                max = Math.max(max, node.cost);
                count++;
            }

            if(count == N - 1){
                break;
            }
        }
        System.out.println(answer - max);
    }

    public static boolean union(int v1, int v2){
        v1 = find(v1);
        v2 = find(v2);

        if(v1 == v2) return false;

        if(parent[v1] < parent[v2]){
            parent[v1] += parent[v2];
            parent[v2] = v1;
        }else{
            parent[v2] += parent[v1];
            parent[v1] = v2;
        }

        return true;
    }

    public static int find(int v){
        if(parent[v] < 0){
            return v;
        }

        return parent[v] = find(parent[v]);
    }
}