Boj 2887 c++ 행성터널

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

 

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

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

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

 

 

이전 문제에서는 각각의 간선에 대한 정보 (두 정점, 가중치) 가 주어졌을 때 최소스패닝 트리를 구성하는 간선들을 선택하는 방식이었다면, 이번에는 정점에 대한 정보만이 주어진다.

 

각각의 정점에 대한 정보 x, y, z좌표에 대한 정보를 통해 두 정점 사이의 거리, 즉 간선의 가중치를 구할 수 있다.

 

하지만 정점은 최대 10만개. 가장 밀집된 경우를  생각할 때 구해야 하는 간선 정보의 가짓수는 100000 x 99999 /2  = 약 49억개가 나와버린다.

 

이를 통해 모든 정점 사이의 거리를 구하는 문제는 아니라는 것을 알 수 있다.

 

정점 사이의 거리를 구하는 방식은 x, y, z좌표의 차 중에서 가장 작은 값만을 취하는 것이다.

 

우리는 여기서 최소스패닝 트리를 이루는 정점들은 각각 x, y, z좌표에 대해서 정렬된 상태의 두 정점 사이의 거리일 것이라는 추측을 할 수 있다.

 

왜냐 ?

 

정점이 N개가 있다고 하면  최소스패닝 트리의 간선은 N-1개가 될 것이다. 정점에 대한 정보를 바탕으로 N-1개의 간선의 가중치 합이 최소가 되도록 트리를 구성해야 할 것이다.

 

사이클이 생기지 않는 범위 내에서 x, y, z좌표가 정렬된 상태에서 인접한 경우, 즉 3*(N-1)가지의 경우만 고려해도 MST를 이룰 수 있는 것이다.

 

증명과정은 복잡하지만 MST의 간선들이 인접한 경우에 반드시 포함된다는 직관을 이용하면 쉽게 풀리는 문제였다.

3차원으로 생각해보면 더 쉽다.

 

마지막으로 3번 계산한 간선들에 대한 정보를 다시 가중치에 대해서 정렬한 후, 분리집합의 성질을 이용해 최소스패닝 트리를 만들어주면 된다.

 

전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, pair<int, int>>> v;
vector<pair<int, int>> v1;
vector<pair<int, int>> v2;
vector<pair<int, int>> v3;
vector<int> parent;

int Find(int x) {
    if(parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    parent[a] = b;
}

void Solve(int N) {
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());

    for(int i = 1; i < N; i++) {
        int a, idxa;
        a = v1[i-1].first;
        idxa = v1[i-1].second;
        int b, idxb;
        b = v1[i].first;
        idxb = v1[i].second;
        v.push_back({abs(a-b), {idxa, idxb}});
    }
    for(int i = 1; i < N; i++) {
        int a, idxa;
        a = v2[i-1].first;
        idxa = v2[i-1].second;
        int b, idxb;
        b = v2[i].first;
        idxb = v2[i].second;
        v.push_back({abs(a-b), {idxa, idxb}});
    }
    for(int i = 1; i < N; i++) {
        int a, idxa;
        a = v3[i-1].first;
        idxa = v3[i-1].second;
        int b, idxb;
        b = v3[i].first;
        idxb = v3[i].second;
        v.push_back({abs(a-b), {idxa, idxb}});
    }

    sort(v.begin(), v.end());

    int cnt = 0, ans = 0;
    for(int i = 0; i < v.size(); i++) {
        if(cnt == N-1)
            break;
        int a, b, c;
        c = v[i].first;
        a = v[i].second.first;
        b = v[i].second.second;

        if(Find(a) == Find(b))
            continue;
        Union(a, b);
        ans += c;
        cnt++;

    }
    cout << ans;
}

int main() {

    int N;
    cin >> N;

    parent.resize(N+1);
    for(int i = 0; i <= N; i++) {
        parent[i] = i;
    }

    for(int i = 0; i < N; i++){
        int x, y, z;
        cin >> x >> y >> z;
        v1.push_back({x, i});
        v2.push_back({y, i});
        v3.push_back({z, i});
    }

    Solve(N);
}