[Baekjoon] 백준 21924번: 도시 건설 (JAVA)

문제 21924

21924번: 도시 건설

[ 문제 풀이 ]

모든 건물을 최소한의 비용으로 연결하는 문제이므로 크루스칼 알고리즘으로 풀면 됩니다. 크루스칼 알고리즘에 대한 자세한 설명은 아래 포스트를 참고해주세요 :)

[JAVA] 서로소 집합(Disjoint Sets)과 연산

절약 비용 = (모든 도로를 설치할 때 드는 비용) - (모든 건물을 연결하는 도로의 최소 비용) 이므로, 입력값에서 비용들을 모두 더한 후, 크루스칼 알고리즘을 이용한 비용을 빼면 됩니다.

모든 건물을 연결할 수 없을 때는 -1을 출력해야 하므로, 사이클이 만들어지지 않는 경우에 한해서 queue에서 뽑은 개수를 카운트하여 이 값이 N-1이 아닌 경우에 -1을 출력하게 하면 됩니다.

[ 코드 ]

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

public class Main {
    private static class Edge implements Comparable<Edge> {
        int start, end, cost;
        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge e) {
            return this.cost - e.cost;
        }
    }

    private static int N, M;
    private static int[] parents;

    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 = new StringTokenizer(br.readLine());
        PriorityQueue<Edge> pq = new PriorityQueue<>();

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

        parents = new int[N+1];

        long totalCost = 0;
        long minimumCost = 0;

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            pq.offer(new Edge(start, end, cost));
            totalCost += cost;
        }

        makeSet();

        int cnt = 0; // 뽑힌 개수
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            int x = findParent(e.start);
            int y = findParent(e.end);
            if (x == y) continue;
            union(x, y);
            minimumCost += e.cost;
            cnt++;
        }

        if (cnt != N-1) {
            bw.write(String.valueOf(-1));
        } else {
            bw.write(String.valueOf(totalCost - minimumCost));
        }
        bw.flush();
    }

    private static void makeSet() {
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
    }

    private static int findParent(int x) {
        if (x == parents[x]) return x;
        else return findParent(parents[x]);
    }

    private static void union(int x, int y) {
        if (x > y) parents[x] = parents[y];
        else parents[y] = parents[x];
    }
}