[백준] BOJ 21924 도시 건설 (골드 4)

문제

---

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

21924: 도시 건설

---

해설

---

1. 이 문제는 크루스칼 알고리즘(유니온 파인트 이용)을 이용하면 간단하게 해결할 수 있는 문제이다.
2. 해당 문제는 전체 도로의 가중치의 합에서 건물을 모두 연결하는 최소 비용의 가중치를 빼주면 된다.
3. 여기서 최소 비용을 구하기 위해서는 크루스칼 알고리즘을 이용하였다.
4. 모든 건물 (정점)을 연결하기 위한 도로의 최소는 무조건 정점 개수 - 1개이다.(최소는 무조건 MST이므로)
5. 이때, 최소를 선택하기 위해 간선의 비용이 최소가 되도록 PQ를 사용하고 UnionFind를 통해
   크루스칼 알고리즘을 구현해 MST를 구해 최소를 구한 후  전체 가중치에서 이를 빼면 절약한 값이다.

---

코드 (크루스칼, 유니온 파인드)

---

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

public class BOJ21924 {
    static int[] parents;
    static int[] rank;
    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());
        parents = new int[N + 1];
        rank = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
            rank[i] = 1;
        }

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        long sum = 0;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            sum += cost;
            pq.offer(new Edge(from, to, cost));
        }

        System.out.println(Kruskal(N, sum, pq));
    }

    private static long Kruskal(int n, long sum, PriorityQueue<Edge> pq) {
        int count = 0;
        long cost = 0;
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            if (count == n - 1) return sum - cost;
            if (union(edge.from, edge.to)) {
                cost += edge.cost;
                count++;
            }
        }
        return -1;
    }

    public static int find(int v){
        if(v == parents[v]) return v;
        return parents[v] = find(parents[v]);
    }

    public static boolean union(int v, int u) {
        int rep1 = find(v);
        int rep2 = find(u);

        if(rep1 == rep2) return false;
        if (rank[rep1] < rank[rep2]) {
            parents[rep1] = rep2;
            return true;
        }
        parents[rep2] = rep1;
        rank[rep1] = rank[rep1] == rank[rep2] ? rank[rep1] + 1 : rank[rep1];
        return true;
    }
}

class Edge implements Comparable<Edge>{
    int from, to, cost;

    public Edge(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.cost, o.cost);
    }
}

---

결론

---

크루스칼을 처음 배우고 문제에 적용할 때마다 바로바로 해결되는 것이 재미있는 것 같다 ꜆₍ᐢ˶•ᴗ•˶ᐢ₎꜆

---