BOJ 2887 행성 터널

www.acmicpc.net/problem/2887

2887번: 행성 터널

 

문제를 요약하자면 MST의 Cost를 구하는 문제이다.

 

단, 이 문제의 값 크기는 1 ≤ N ≤ 100,000 로 Naive하게 모든 행성들의 간선 거리를 구하려고 한다면 10^15가 되어 시간내에 풀지 못할 것이다.

 

이 문제에서 잘 봐야할 것은 터널을 연결할 때 드는 비용이다.

"두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)" 에서 

 

터널을 연결하기 위해서는 3개의 축을 한꺼번에 볼 필요가 없다는 것을 알 수 있다

즉, 한 행성에서 터널로 연결하는데 드는 비용은 (X축을 기준으로 가장 가까운 행성간 거리), (Y축을 기준으로 가장 가까운 행성간 거리), (Z축을 기준으로 가장 가까운 행성간 거리) 중 하나이다.

저것들을 어떻게 구할까?

나는 각 축 좌표에 대해 정렬을 이용하여 구했고, 배열중 서로 인접한 값들 (예를 들어 arr[0]-arr[1],  arr[12]-arr[13]) 을 edge로 만들어 MST Cost 계산에 필요한 edge들만 사용하도록 했다.

(X좌표를 기준으로한 edge), (Y좌표를 기준으로한 edge), (Z좌표를 기준으로한 edge) 를 이용하여 크루스칼 알고리즘을 사용하면 문제를 시간 내에 풀 수 있다.

 

아래는 나의 코드이다.

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

using namespace std;


int n;
vector<pair<int, pair<int, int>>> edge;

// parent[now] = 0 : root node
int parent[100001];
int cost  [100001];

int find(int now){
    if(parent[now]){
        return parent[now] = find(parent[now]);
    }
    else{
        return now;
    }
}


int merge(int a, int b, int c){

    a = find(a);
    b = find(b);

    if(a == b) return cost[a];
    else{
        parent[b] = a;
        cost[a] += (cost[b] + c);
        return cost[a];
    }
}



int main(){

    vector<pair<int, int>> point[3];

    int v;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            scanf("%d",&v);
            point[j].push_back({v,i+1});
        }
    }

    for(int i=0;i<3;i++){
        sort(point[i].begin(), point[i].end());
        int vsize = point[i].size();
        for(int j=0;j<vsize-1;j++){
            edge.push_back({ abs(point[i][j].first - point[i][j+1].first), 
                            {point[i][j].second, point[i][j+1].second}});
        }
    }

    sort(edge.begin(), edge.end());
    int answer = 0;
    for(auto a : edge){
        answer = merge(a.second.first, a.second.second, a.first);
    }

    printf("%d\n",answer);

    return 0;
}