백준) 2887 행성 터널

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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

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

예제 입력 

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

예제 출력 

4

1. 접근

모든 터널을 연결하는데 필요한 최소비용을 구하는 최소신장트리 문제이다.

크루스칼 알고리즘을 사용하자.

2. 풀이

간선을 고르는게 문제다.

A터널과 B터널의 연결은 x, y, z 좌표 중에 차이가 가장 작은 축으로 이루어진다.

단순히 N^2 으로 모든 터널을 만들어 본 다음에 크루스칼을 돌려볼 수 있지만, 시간제한이 문제다.

그러면 다음으로 떠오르는 생각은 정렬을 통해 N * log n 으로 해결할 방법을 찾아보는 것이다.

정렬이후 i, i - 1 행성의 차이로 터널을 만들어 보자. 그러면 총 3 * (N - 1) 개의 터널이 생길 것이다.

이 후 크루스칼을 돌리면 된다.

왜 이 방법이 최소신장트리의 모든 간선을 놓치지 않는 걸까?

단순히 x 축만 사용한다고 생각해보자. ( x = 0, 3, 4, 8, 13, 14 ) 

정렬 이후에 이웃 행성들 끼리만 터널을 만든다면 바로 0~14 까지 일렬로 쭈욱 터널이 생긴다.

바로 최소신장트리를 만들 수 있다. 이 간선들 외에 다른 최소신장 트리를 만드는 방법은 없다.

따라서 축을 세 개 쓴다고 해도 이는 변하지 않는다.

다만 쓸데 없는 간선이 2 * (N - 1)개 추가될 뿐이다.

정답인 N - 1 개의 간선은 놓쳐지지 않고 포함된다.

참고 : http://js1jj2sk3.tistory.com/22

3. 코드

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
 
struct planet {
    int x, y, z, num;
};
bool cmpx(const planet& p1, const planet& p2) {
    return p1.x > p2.x;
}
bool cmpy(const planet& p1, const planet& p2) {
    return p1.y > p2.y;
}
bool cmpz(const planet& p1, const planet& p2) {
    return p1.z > p2.z;
}
planet pl[100000];
 
struct edge {
    int weight, from, to;
};
bool operator<(const edge& e1, const edge& e2) {
    return e1.weight > e2.weight;
}
vector<edge> ed;
 
 
int parent[100000];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
 
    parent[x] = y;
}
 
int n, i;
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i) {
        scanf("%d %d %d", &pl[i].x, &pl[i].y, &pl[i].z);
        pl[i].num = i;
        parent[i] = i;
    }
 
    sort(pl, pl + n, cmpx);
    for (i = 0; i < n - 1; ++i)
        ed.push_back({ abs(pl[i].x - pl[i + 1].x), pl[i].num, pl[i + 1].num });
 
    sort(pl, pl + n, cmpy);
    for (i = 0; i < n - 1; ++i)
        ed.push_back({ abs(pl[i].y - pl[i + 1].y), pl[i].num, pl[i + 1].num });
 
    sort(pl, pl + n, cmpz);
    for (i = 0; i < n - 1; ++i)
        ed.push_back({ abs(pl[i].z - pl[i + 1].z), pl[i].num, pl[i + 1].num });
 
    sort(ed.begin(), ed.end());
 
    int ans = 0;
    int cnt = 0;
    for (int i = ed.size() - 1; cnt != n - 1;--i) {
        if (find(ed[i].from) != find(ed[i].to)) {
            cnt++;
            ans += ed[i].weight;
 
            unite(ed[i].from, ed[i].to);
        }
        if (cnt == n - 1)
            break;
    }
    printf("%d", ans);
 
    return 0;
}