BOJ#2887 행성 터널

BOJ#2887 행성 터널

* 문제

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

* 풀이

MST, 최소 스패닝 트리 문제입니다.

최소 스패닝 트리의 특성상 (문제에도 명시되어 있듯이) 행성이 N개 이므로, 간선은 N-1개가 됩니다.

이 문제를 풀 때 어려웠던 점은 간선 정보가 직접적으로 주어지지 않고

직접 간선 정보를 만들어야 한다는 점입니다.

주의할 점으로는

N이 최대 100,000 이므로 모든 간선을 입력하려면 100,000 * 100,000이 됩니다. (시간 초과)

따라서 모든 간선을 추가할 수 없으므로, 아래 방법대로 최소 간선만 추가해줍니다.

간선 비용은 문제에 주어진대로 min(x좌표 차이, y좌표 차이, z좌표 차이) 이므로

1. x좌표를 기준으로 정렬 -> i-1 노드와 i 노드의 간선 정보 추가

2. y좌표를 기준으로 정렬 -> i-1 노드와 i 노드의 간선 정보 추가 

3. z좌표를 기준으로 정렬 -> i-1 노드와 i 노드의 간선 정보 추가

이후 크루스칼 알고리즘과 유니온-파인드 자료구조를 이용하여 MST 문제를 풀면 됩니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/1d6cbc6dc6fce620ee93c448975f1d4e0cbbe6a3/BOJ%232887_SVEMIR/src/Main.java

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;

/**
 * BOJ#2887 SVEMIR 행성 터널
 * https://www.acmicpc.net/problem/2887
 */

public class Main {

    public static void main(String[] args) throws IOException {

        // input
        int N; // 행성의 개수, N <= 100,000
        Planet[] p;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        p = new Planet[N];

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            p[i] = new Planet(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), i);
        }

        // solve - Kruskal
        PriorityQueue<Edge> edgePQ = new PriorityQueue<>();

        // x좌표를 기준으로 정렬, 간선 추가
        Comparator<Planet> cp = (o1, o2) -> o1.x < o2.x ? -1 : 1;

        Arrays.sort(p, cp);
        for (int i = 1; i < N; i++) {

            edgePQ.add(new Edge(p[i - 1].idx, p[i].idx, Math.abs(p[i].x - p[i - 1].x)));
        }

        // y좌표를 기준으로 정렬, 간선 추가
        cp = (o1, o2) -> o1.y < o2.y ? -1 : 1;

        Arrays.sort(p, cp);
        for (int i = 1; i < N; i++) {

            edgePQ.add(new Edge(p[i - 1].idx, p[i].idx, Math.abs(p[i].y - p[i - 1].y)));
        }

        // z좌표를 기준으로 정렬, 간선 추가
        cp = (o1, o2) -> o1.z < o2.z ? -1 : 1;

        Arrays.sort(p, cp);
        for (int i = 1; i < N; i++) {

            edgePQ.add(new Edge(p[i - 1].idx, p[i].idx, Math.abs(p[i].z - p[i - 1].z)));
        }

        UnionFind unionFind = new UnionFind(N);
        int nEdge = 0;
        int cost = 0;

        while (nEdge < N && !edgePQ.isEmpty()) {

            Edge edge = edgePQ.poll();

            if (unionFind.find(edge.A) != unionFind.find(edge.B)) {

                unionFind.union(edge.A, edge.B);
                nEdge++;
                cost += edge.cost;
            }
        }

        System.out.println(cost);
    }
}

class Planet {

    int x, y, z;
    int idx;

    Planet(int x, int y, int z, int idx) {

        this.x = x;
        this.y = y;
        this.z = z;

        this.idx = idx;
    }
}

class Edge implements Comparable<Edge> {

    int A, B;
    int cost;

    Edge(int A, int B, int cost) {

        this.A = A;
        this.B = B;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge o) {

        return this.cost < o.cost ? -1 : 1;
    }
}

class UnionFind {

    private int[] root;

    UnionFind(int V) {

        root = new int[V + 1];

        initialize();
    }

    int find(int a) {

        if (root[a] < 0) {

            return a;
        }

        return root[a] = find(root[a]);
    }

    void union(int a, int b) {

        int root1 = find(a);
        int root2 = find(b);

        if (root1 == root2) {

            return;
        }

        if (root[root1] > root[root2]) {

            root1 ^= root2;
            root2 ^= root1;
            root1 ^= root2;
        }

        root[root1] += root[root2];
        root[root2] = root1;
    }

    private void initialize() {

        for (int i = 0; i < root.length; i++) {

            root[i] = -1;
        }
    }
}