[BOJ/MST] 백준 2887 - 행성 터널 (Java)

백준 2887 - 행성 터널

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

문제

행성은 3차원 좌표 위의 한 점
행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용  min(|xA - xB|, |yA - yB|, |zA - zB|)
터널을 총 N - 1개 건설해서 모든 행성이 서로 연결되게 하려고 함

입력
첫째 줄: 행성의 개수 N (1 <= N <= 100,000)
다음 N개 줄: 각 행성의 x, y, z 좌표 ($-10^9$ <= 좌표 <= $10^9$)
출력: 모든 행성을 터널로 연결하는데 필요한 최소 비용

---

풀이

Planet 클래스

행성 번호 + x, y, z 좌표 저장

static class Planet {
    int idx, x, y, z;

    Planet(int idx, int x, int y, int z) {
        this.idx = idx;
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

 

Edge 클래스

행성 u, v 사이의 간선, 비용 저장

static class Edge implements Comparable<Edge> {
    int u, v, cost;

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

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

 

두 행성 A, B 연결 비용 = min( |xA - xB|, |yA - yB|, |zA - zB| )

-> `cost = Math.min(Math.min(|x1 - x2|, |y1 - y2|), |z1 - z2|)`

모든 행성 쌍($N^2$)에 대해 계산?

-> 100,000 * 100,000 = 10,000,000,000 = 10억 번 연산 But, N <= 100,000

=> 두 행성이 서로 연결될 때 가장 작은 차이(x or y or z)만 비용으로 사용

 

3(N-1)개 간선 모두 edges에 넣고 오름차순으로 정렬

// x 기준 정렬
Arrays.sort(arr, Comparator.comparingInt(a -> a.x));
for (int i = 0; i < N - 1; i++) {
    edges.add(new Edge(arr[i].idx, arr[i + 1].idx, Math.abs(arr[i].x - arr[i + 1].x)));
}

// y 기준 정렬
Arrays.sort(arr, Comparator.comparingInt(a -> a.y));
for (int i = 0; i < N - 1; i++) {
    edges.add(new Edge(arr[i].idx, arr[i + 1].idx, Math.abs(arr[i].y - arr[i + 1].y)));
}

// z 기준 정렬
Arrays.sort(arr, Comparator.comparingInt(a -> a.z));
for (int i = 0; i < N - 1; i++) {
    edges.add(new Edge(arr[i].idx, arr[i + 1].idx, Math.abs(arr[i].z - arr[i + 1].z)));
}

Collections.sort(edges);

---

코드

import java.io.*;
import java.util.*;

// 행성 터널
public class boj_2887 {
    static class Planet {
        int idx, x, y, z;

        Planet(int idx, int x, int y, int z) {
            this.idx = idx;
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    static class Edge implements Comparable<Edge> {
        int u, v, cost;

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

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

    static int N;
    static int[] unf;
    static List<Edge> edges = new ArrayList<>();

    static int find(int x) {
        if (x == unf[x]) return x;
        return unf[x] = find(unf[x]);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) unf[b] = a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        Planet[] arr = new Planet[N];
        unf = new int[N];
        for (int i = 0; i < N; i++) unf[i] = i;

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

            arr[i] = new Planet(i, x, y, z);
        }

        Arrays.sort(arr, Comparator.comparingInt(a -> a.x));
        for (int i = 0; i < N - 1; i++) {
            edges.add(new Edge(arr[i].idx, arr[i + 1].idx, Math.abs(arr[i].x - arr[i + 1].x)));
        }

        Arrays.sort(arr, Comparator.comparingInt(a -> a.y));
        for (int i = 0; i < N - 1; i++) {
            edges.add(new Edge(arr[i].idx, arr[i + 1].idx, Math.abs(arr[i].y - arr[i + 1].y)));
        }

        Arrays.sort(arr, Comparator.comparingInt(a -> a.z));
        for (int i = 0; i < N - 1; i++) {
            edges.add(new Edge(arr[i].idx, arr[i + 1].idx, Math.abs(arr[i].z - arr[i + 1].z)));
        }

        Collections.sort(edges);

        int minCost = 0;
        for (Edge e : edges) {
            if (find(e.u) != find(e.v)) {
                union(e.u, e.v);
                minCost += e.cost;
            }
        }

        System.out.println(minCost);
    }
}