행성 터널 (BOJ 2887)

문제

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

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(x_A, y_A, z_A)와 B(x_B, y_B, z_B)를 터널로 연결할 때 드는 비용은 min(|x_A-x_B|, |y_A-y_B|, |z_A-z_B|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -10⁹보다 크거나 같고, 10⁹보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

출력

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

예제 입력

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

예제 출력

문제 풀이

최소 스패닝 트리 (MST) 로 풀면 된다.
그래프 구성만 하고 MST 알고리즘 돌리면 된다.

답안 코드

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_V   100000

int V;
vector<pair<long long, pair<int,int>>> edges;

pair<int,int> x[MAX_V], y[MAX_V], z[MAX_V];

int unionGroup[MAX_V];

int find(int i){
    while(unionGroup[i] != i)   i = unionGroup[i] = unionGroup[unionGroup[i]];
    return i;
}
void unionSet(int u, int v){
    unionGroup[find(u)] = find(v);
}
bool isUnion(int u, int v){
    return find(u) == find(v);
}

int main(){
    scanf("%d", &V);
    for(int i = 0; i < V; ++i){
        scanf("%d %d %d", &x[i].first, &y[i].first, &z[i].first);
        x[i].second = y[i].second = z[i].second = i;
    }
    
    sort(x, x+V);
    sort(y, y+V);
    sort(z, z+V);
    for(int i = 1; i < V; ++i){
        edges.push_back(make_pair(x[i].first-x[i-1].first, make_pair(x[i].second, x[i-1].second)));
        edges.push_back(make_pair(y[i].first-y[i-1].first, make_pair(y[i].second, y[i-1].second)));
        edges.push_back(make_pair(z[i].first-z[i-1].first, make_pair(z[i].second, z[i-1].second)));
    }
    
    long long mst_cost = 0;
    sort(edges.begin(),edges.end());
    for(int i = 0; i < V; ++i)
        unionGroup[i] = i;
    for(int i = 0; i < edges.size(); ++i){
        auto e = edges[i].second;
        if(!isUnion(e.first, e.second)){
            mst_cost += edges[i].first;
            unionSet(e.first, e.second);
        }
    }
    
    printf("%lld\n", mst_cost);
    
    return 0;
}