백준 2887 [행성터널]

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 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좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

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

2887번: 행성 터널

 

---

 이번 문제는 보자마자 MST(최소 신장 트리)문제라는 것을 한번에 알아차렸다. 하지만 보통 간선의 개수와 비용을 주던 다른 문제들과 달리 행성 터널에서는 정점의 좌표들만 주고 간선의 비용은 계산하는 법만 알려줬다.

 모든 정점사이의 거리를 전부 고려하여 계산하면 시간 초과가 발생하기 때문에 어떻게 간선의 개수를 최소화할지 생각하는게 이번 문제의 핵심 포인트였다. 그래서 나는 한 행성에서 x좌표 기준으로 +방향으로 가장 가까운 행성과의 간선, -방향으로 가장 가까운 행성과의 간선 이렇게 2개의 간선과 이를 y, z좌표를 기준으로 똑같이 적용 하였을때 찾을 수 있는 각각의 간선 2개씩을 합쳐 1개의 행성당 6개의 간선만을 고려하였다. 풀이 과정은 다음과 같다.

 

    1. ArrayList를 X, Y, Z 이렇게 3개를 만든다.

    2. 행성의 좌표를 입력받으면 입력받은 x, y, z 값을 각각 X, Y, Z ArrayList에 넣는다.

    3. X, Y, Z를 오름차순으로 정렬한다.

    4. 각각의 ArrayList의 요소 값의 차이를 이용하여  PriorityQueue에 간선을 집어넣는다.

    5. 만든  PriorityQueue를 이용하여 크루스칼 알고리즘을 적용하여 문제를 해결한다.

 

여기서 ArrayList나 PriorityQueue에는 다음과 같은 구조체를 사용한다.

class Planet implements Comparable<Planet>{
    int from;
    int to;
    int val;
    Planet(int f, int t, int v){
        from = f;
        to = t;
        val = v;
    }
    @Override
    public int compareTo(Planet o){
        return (this.val - o.val);
    }
}

 

백준에서 제공하는 기본 테스트케이스를 기준으로 한번 설명을 해보면 다음과 같다.

 

예제 입력)

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

 

 

    1. ArrayList를 X, Y, Z 이렇게 3개를 만든다.

 

index	0	1	2	3	4
X
Y
Z

 

 

    2. 행성의 좌표를 입력받으면 입력받은 x, y, z 값을 각각 X, Y, Z ArrayList에 넣는다.

 

index	0	1	2	3	4
X	11 (1번 행성)	14 (2번 행성)	-1 (3번 행성)	10 (4번 행성)	19 (5번 행성)
Y	-15 (1번 행성)	-5 (2번 행성)	-1 (3번 행성)	-4 (4번 행성)	-4 (5번 행성)
Z	-15 (1번 행성)	-15 (2번 행성)	-5 (3번 행성)	-1 (4번 행성)	19 (5번 행성)

   

 

    3. X, Y, Z를 오름차순으로 정렬한다.

 

index	0	1	2	3	4
X	-1 (3번 행성)	10 (4번 행성)	11 (1번 행성)	14 (2번 행성)	19 (5번 행성)
Y	-15 (1번 행성)	-5 (2번 행성)	-4 (4번 행성)	-4 (5번 행성)	-1 (3번 행성)
Z	-15 (1번 행성)	-15 (2번 행성)	-5 (3번 행성)	-1 (4번 행성)	19 (5번 행성)

 

 

    4. 각각의 ArrayList의 요소 값의 차이를 이용하여  PriorityQueue에 간선을 집어넣는다.

 

       (우선순위 큐를 q = {(행성 1, 행성 2, cost) , ....} 라고 표현)

 

ArrayList X

   1. index 0번과 1번의 val 차이가 11이므로 q = {(3, 4, 11)}

   2. index 1번과 2번의 val 차이가 1이므로 q = {(4, 1, 1), (3, 4, 11)} ( ∵  우선순위 큐안에서 구조체 Planet이 cost기준으로 오름차순 정렬)

   3. index 2번과 3번의 val 차이가 3이므로 q = {(4, 1, 1), (1, 2, 3), (3, 4, 11)}

   4. index 3번과 4번의 val 차이가 5이므로 q = {(4, 1, 1), (1, 2, 3), (2, 5, 5), (3, 4, 11)}

 

이런식으로 Y, Z에 있는 간선들도 우선순위 큐에 집어넣으면 된다.

 

 

    5. 만든  PriorityQueue를 이용하여 크루스칼 알고리즘을 적용하여 문제를 해결한다.

 

이제 5번 부터는 순수 크루스칼 알고리즘 적용이므로 추가 설명을 하지는 않겠다.

 

코드는 다음과 같다.

 

import java.io.*;
import java.util.*;
class Planet implements Comparable<Planet>{
    int from;
    int to;
    int val;
    Planet(int f, int t, int v){
        from = f;
        to = t;
        val = v;
    }
    @Override
    public int compareTo(Planet o){
        return (this.val - o.val);
    }
}
public class Main {
    static int[] g;
    static int find (int x){
        if (g[x] == x) return x;
        else return g[x] = find(g[x]);
    }

    static boolean union(int x, int y) {
        int a = find(x);
        int b = find(y);
        if (a == b) return false;
        else if (a > b)
            g[a] = b;
        else
            g[b] = a;
        return true;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        g = new int[n + 1];
        ArrayList<Planet> X = new ArrayList<>();
        ArrayList<Planet> Y = new ArrayList<>();
        ArrayList<Planet> Z = new ArrayList<>();
        for (int i = 1; i < n + 1 ;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());
            X.add(new Planet(i, 0, x));
            Y.add(new Planet(i, 0, y));
            Z.add(new Planet(i, 0, z));
            g[i] = i;
        }
        Collections.sort(X);
        Collections.sort(Y);
        Collections.sort(Z);
        PriorityQueue<Planet> q = new PriorityQueue<>();
        for (int i = 0; i < n; i++){
            if (i != 0) {
                q.add(new Planet(X.get(i).from, X.get(i - 1).from, Math.abs(X.get(i).val - X.get(i - 1).val)));
                q.add(new Planet(Y.get(i).from, Y.get(i - 1).from, Math.abs(Y.get(i).val - Y.get(i - 1).val)));
                q.add(new Planet(Z.get(i).from, Z.get(i - 1).from, Math.abs(Z.get(i).val - Z.get(i - 1).val)));
            }
            if (i != n - 1){
                q.add(new Planet(X.get(i).from, X.get(i + 1).from, Math.abs(X.get(i).val - X.get(i + 1).val)));
                q.add(new Planet(Y.get(i).from, Y.get(i + 1).from, Math.abs(Y.get(i).val - Y.get(i + 1).val)));
                q.add(new Planet(Z.get(i).from, Z.get(i + 1).from, Math.abs(Z.get(i).val - Z.get(i + 1).val)));
            }
        }
        long cost = 0;
        while (!q.isEmpty()){
            Planet p = q.poll();
            if (union(p.from, p.to)){
                cost += p.val;
            }
        }
        System.out.println(cost);
    }
}