백준 21924 - 도시 건설

문제

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

리뷰

크루스칼을 이용해 풀이할 수 있는 간단한 문제였다.

문제에서 요구하는 것은 아래와 같다.

주어진 전체 간선 비용 합 - MST 구성 간선 비용 합

따라서, 입력을 받으며 간선 비용의 합을 구하고 크루스칼을 통해 MST를 형성하며
총 간선 비용의 합에서 채택된 간선의 비용을 빼주어 답을 구하였다.

문제에서 유의할 점은 건물의 개수($N$)이 최대 $10^5$이고 비용($c$)이 최대 $10^6$이기 때문에
간선 비용 합을 저장하는 변수의 타입을 int로 할 경우 오버플로우가 발생할 수 있다는
점이었다.

로직의 시간복잡도는 크루스칼의 $O(MlogM)$으로 수렴하고 이는 $M=5\times 10^5$인
최악의 경우에도 제한 조건 1초를 무난히 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.w));

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

        parent = new int[N + 1];
        int u, v, w;
        long costSum = 0;

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = parseInt(st.nextToken());

            pq.offer(new Edge(u, v, w));
            costSum += w;
        }

        System.out.println(kruskal(N, costSum));
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

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

    static long kruskal(int N, long costSum) {
        Arrays.fill(parent, -1);
        int selectEdges = 0;

        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            int r1 = find(e.u);
            int r2 = find(e.v);

            if (r1 == r2) continue;

            if (parent[r1] < parent[r2]) {
                parent[r1] += parent[r2];
                parent[r2] = r1;
            } else {
                parent[r2] += parent[r1];
                parent[r1] = r2;
            }

            selectEdges++;
            costSum -= e.w;

            if (selectEdges == N - 1)
                return costSum;
        }

        return -1;
    }

    static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }
}

결과