[Algo] 백준 21924 도시 건설 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/21924

메모리 : 162984KB

시간 : 1196ms

언어 : Java 11

---

코드

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

public class Main {
    static class Node {
        int a, b, cost;

        Node(int a, int b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }
    }

    static PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.cost - o2.cost;
        }

    });
    static int[] parent;
    static long mini;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        long all = 0;
        mini = 0;
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            all += c;
            pq.add(new Node(a, b, c));
        }
        if (kruskal()) {
            System.out.println(all - mini);
        } else {
            System.out.println(-1);
        }
    }

    private static boolean kruskal() {
        int cnt = 0;
        while (!pq.isEmpty()) {
            Node n = pq.poll();
            if (find(n.a) != find(n.b)) {
                union(n.a, n.b);
                mini += n.cost;
                cnt++;
            }
            if (cnt == N - 1)
                return true;
        }
        return false;
    }

    private static void union(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x <= y) {
            parent[y] = x;
        } else if (x > y) {
            parent[x] = y;
        }
    }

    private static int find(int n) {
        if (parent[n] == n)
            return n;
        else
            return parent[n] = find(parent[n]);
    }
}

풀이

크루스칼 문제. 크루스칼은 그리디알고리즘의 일종으로 그래프의 간선을 가중치의 오름차순으로 정렬해 놓은 뒤 사이클을 형성하지 않는 선에서 정렬된 순서대로 간선을 선택한다. 정렬을 위해 Priority Queue를 사용한다. 사이클이 형성된다는 것은 불필요한 간선이라는 뜻이다. 우선순위 큐를 이용해 최소값끼리 이미 연결해놨으니 사이클이 형성되는 간선은 선택하면 안된다. 사이클을 판단하기 위해서 Union-Find를 활용한다. union은 정점을 묶어주는 함수이고, find는 해당 정점의 루트정점을 찾아주는 함수이다.