2887번 행성 터널

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

2887번: 행성 터널

최소 스패닝 트리 문제이다.
모든 경로의 거리를 배열에 담아두면 100,000 * 100,000이므로 메모리 초과가 난다. 따라서 x,y,z를 따로 두어 비용이 가장 가깝도록 각 좌표마다 정렬을 시킨다.
예를 들어 x의 좌표가 3(A) 2(B) 10(C) 5(D)였다면 x 좌표를 정렬 시킨 후 2(B) 3(A) 5(D) 10(C)가 되고

B -> A로 가는 비용 1

A -> D로 가는 비용 2

D -> C로 가는 비용 5

이런식으로 하는 이유는 각 거리는 min( { abs(x - x1), abs(y - y1), abs(z - z1) } )이기 때문에 가장 작은 값만 가져오면 된다.

이후 각 정보를 저장시켜 크루스칼 알고리즘을 이용해준다.

#include <bits/stdc++.h>
#define l long long
#define INF 2e9
#define p pair<int,int>
#define vc vector<int>
#define F first
#define S second
using namespace std;

int root[100001];

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

void Union(int x,int y){
    x = Find(x), y = Find(y);

    if(x < y) root[y] = x;
    else root[x] = y;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n,a,b,c,ans = 0;

    cin >> n;

    p x[n],y[n],z[n];

    vector<tuple<int,int,int>> v;

    for(int i=0;i<n;i++) {
        cin >> a >> b >> c;
        root[i] = i;

        x[i] = {a,i};
        y[i] = {b,i};
        z[i] = {c,i};
    }

    sort(x,x+n);
    sort(y,y+n);
    sort(z,z+n);

    for(int i=0;i<n-1;i++){
        v.emplace_back(x[i+1].F - x[i].F,x[i].S,x[i+1].S);
        v.emplace_back(y[i+1].F - y[i].F,y[i].S,y[i+1].S);
        v.emplace_back(z[i+1].F - z[i].F,z[i].S,z[i+1].S);
    }

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

    for(auto &i : v){
        tie(a,b,c) = i;

        if(Find(b) == Find(c)) continue;
        Union(b,c);

        ans += a;
    }

    cout << ans;
}