백준 28473 - 도로 위의 표지판

문제

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

리뷰

크루스칼을 통해 풀이할 수 있는 문제였다.

기존에 간선의 비용이 크루스칼에서 MST를 구성하는데 우선시 되는 기준이었다면
이 문제에서는 간선 정보에 z 라는 1~9 범위의 숫자가 추가되고 이 숫자가 작은
순으로 간선을 채택해야 하는 조건이 부가적으로 주어졌다.

따라서 크루스칼에 사용할 간선을 저장하는 최소힙에 z를 기준으로 하도록
Comparator를 구현하고, 한편 z를 기준으로 채택하면서도 총 비용도 최소화해야
하므로 해당 조건 역시, Comparator내에서 z가 같을 시 비용(w)을 비교하여
정렬하도록 로직을 구성했다.

이후, 크루스칼을 수행하며 채택된 간선들의 z를 List에 저장하고, 총 비용을
도출하면 답을 구할 수 있다.

로직의 시간복잡도는 크루스칼의 $O(NlogM)$으로 수렴하고 이는 $N=200,000$,
$M=500,000$인 최악의 경우에도 무난히 제한 조건 2초를 통과할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.*;

public class Main {
    static int[] parent;
    static PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> {
        if (e1.z == e2.z) return compare(e1.w, e2.w);

        return compare(e1.z, e2.z);
    });

    static List<Integer> answer = new ArrayList<>();

    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 x, y, z, w;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = parseInt(st.nextToken());
            y = parseInt(st.nextToken());
            z = parseInt(st.nextToken());
            w = parseInt(st.nextToken());

            pq.offer(new Edge(x, y, z, w));
        }

        long sum = kruskal(N);
        if (sum == -1) System.out.println(sum);
        else {
            answer.sort(Comparator.comparingInt(n -> n));
            StringBuilder ans = new StringBuilder();
            for (Integer num : answer) {
                ans.append(num);
            }
            System.out.println(ans + " " + sum);
        }

        br.close();
    }

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

        while (!pq.isEmpty() && selected < N - 1) {
            Edge e = pq.poll();

            if (!union(e.x, e.y)) continue;

            selected++;
            answer.add(e.z);
            sum += e.w;
        }

        return selected == N - 1 ? sum : -1;
    }


    static boolean union(int x, int y) {
        int r1 = find(x);
        int r2 = find(y);

        if (r1 == r2) return false;

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

        return true;
    }

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

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

    static class Edge {
        int x, y, z, w;

        public Edge(int x, int y, int z, int w) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.w = w;
        }
    }
}

결과