백준 2887 - 행성 터널

문제

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

리뷰

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

주어진 문제를 풀이하기 위해 관건이 되는 부분은 간선을 형성하는 로직이었다.
모든 $x$, $y$, $z$의 각 $x_A$, $x_B$ 꼴의 조합을 통해 간선을 형성하려 하면,
로직의 시간복잡도가 $O(N^2)$로 수렴하므로, $N=100,000$인 최악의 경우
약 10억 번(=10초) 연산을 수행하게 되어 제한 조건을 통과하지 못한다.

따라서 $x$, $y$ ,$z$ 각 조합중 최소의 $x_A - x_B$ 값을 가지게 되는 경우를
생각해보아야 했다. 결론적으로 각 좌표값을 저장한 후, 정렬하여 $|x_i-x_{i+1}|$
값을 구하게 되면 ($0 \leq i\leq N-2$) 최소의 좌표 차이를 띄는 쌍들을
도출할 수 있다. 또한, 가장 빠른 정렬 알고리즘을 채택할 경우 좌표값을 정렬하는
시간복잡도는 $O(NlogN)$으로 수렴하므로, $N=100,000$인 최악의 경우에도
제한 조건을 초과하지 않는다.

위 아이디어를 바탕으로 로직을 구성하기 위해 우선 인덱스(idx)와
좌표값(value)을 저장할 Point 클래스를 정의하고 각 행성의 좌표값을 해당
클래스 타입 배열을 통해 각각 저장하였다.

이후, 각 좌표값 배열을 값을 기준으로 오름차순 정렬한 후, $|x_i-x_{i+1}|$
($0\leq i \leq N-2$, $y$, $z$의 경우도 마찬가지) 값을 비용으로 하여
간선을 표현하는 Edge 클래스를 통해 비용 기준 최소힙에 간선 정보를 저장했다.

마지막으로, 크루스칼을 통해 $N-1$개의 간선을 채택해 MST를 형성하며
비용을 계산하여 답을 구했다.

로직의 시간복잡도는 크루스칼 부분에서 $O(Nlog3N)$으로 수렴하므로
(좌표별로 간선을 $N$개씩 형성하여 최소힙에 저장하기 때문에)
$N=100,000$인 최악의 경우에도 무난히 제한 조건 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.parseInt;

public class Main {
    static int[] parent;
    static Point[] xValues, yValues, zValues;
    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));
        int N = parseInt(br.readLine());
        parent = new int[N];
        xValues = new Point[N];
        yValues = new Point[N];
        zValues = new Point[N];

        StringTokenizer st;
        int x, y, z;
        for (int i = 0; i < parent.length; i++) {
            st = new StringTokenizer(br.readLine());
            x = parseInt(st.nextToken());
            y = parseInt(st.nextToken());
            z = parseInt(st.nextToken());

            xValues[i] = new Point(i, x);
            yValues[i] = new Point(i, y);
            zValues[i] = new Point(i, z);
        }

        Comparator<Point> comp = Comparator.comparingInt(p -> p.value);
        Arrays.sort(xValues, comp);
        Arrays.sort(yValues, comp);
        Arrays.sort(zValues, comp);
        saveEdges();
        long sum = kruskal(N);
        System.out.println(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.u, e.v)) continue;

            selected++;
            sum += e.w;
        }

        return sum;
    }

    static void saveEdges() {
        for (int i = 0; i < xValues.length - 1; i++) {
            pq.offer(new Edge(xValues[i].idx, xValues[i + 1].idx, Math.abs(xValues[i].value - xValues[i + 1].value)));
            pq.offer(new Edge(yValues[i].idx, yValues[i + 1].idx, Math.abs(yValues[i].value - yValues[i + 1].value)));
            pq.offer(new Edge(zValues[i].idx, zValues[i + 1].idx, Math.abs(zValues[i].value - zValues[i + 1].value)));
        }
    }

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

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

    static boolean union(int u, int v) {
        int r1 = find(u);
        int r2 = find(v);

        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 class Point {
        int idx, value;

        public Point(int idx, int value) {
            this.idx = idx;
            this.value = value;
        }
    }

    static class Edge {
        int u, v, w;

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

결과