문제 요약

3차원 좌표 노드 (x, y, z) N개가 주어질때, 모든 노드를 최소 비용으로 연결시켜라.
비용은 min(|x1 - x2|, |y1 - y2|, |z1 - z2|) 이다.

해설

모든 노드를 최소비용으로 연결하는 Minimum Spanning Tree를 만드는 문제이다.
MST를 만드는 알고리즘은 크루스칼, 프림 알고리즘이 있다. 그리고 이 알고리즘들을 사용하기 위해서는 일단 간선의 정보를 저장해야 한다.

하지만 이 문제에서는 모든 간선을 생각하면, 1<=N<=1e-5이므로 1e-10개의 간선이 나오게 된다.
그러므로 간선을 줄이는 테크닉을 생각하여 MST를 구하면 풀리는 문제이다.

그렇다면 간선을 어떻게 줄여야할까,
간선의 가중치 min(|x1 - x2|, |y1 - y2|, |z1 - z2|) 를 사용해야 한다.
결국 MST를 만드는 알고리즘은 그리디 기반으로 가중치가 작은 간선들만 생각한다. 그리고 각각의 간선의 가중치는 x,y,z의 차의 최솟값이 된다. 그러므로 모든 노드를 x, y, z로 분리하고, 오름/내림차순으로 정렬한 후에 x, y, z에 따른 간선을을 만들어서 모든 간선을 저장한다. 그 후 모든 간선을 정렬하여 가장 작은 가중치를 가진 간선부터 체크해주면 되는 것 이다.

좌표를 나누어 정렬하여 간선을 줄이는 것이 가능한 이유는
x1, x2, x3가 오름차순 정렬이 되어있다고 가정했을때 x1 < x2 < x3가 된다.
x2 -> x1, x3 -> x2가 x3 -> x1, x3 -> x2보다 작은거를 증명하는 것으로 예시를 들면

x2 - x1 + x3 - x2 < x3 - x1 + x3 - x2
x3 - x1 < 2*x3 - x1 - x2
x2 < x3가 된다. 전제 조건에 따라 x2 < x3이므로, 오름차순인 경우 순차적인 간선을 만드는 것이 가장 작은 간선들인 것을 알 수 있다.

그러므로 모든 좌표에 대한 간선을 만들고 크루스칼 알고리즘을 시행해주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define pii pair<int,int> 
#define ll long long
using namespace std;
long long N, check[100001], ans;
vector<pii>xv;  
vector<pii>yv;
vector<pii>zv;
vector<pair<ll,pii > >edges;
int Find(int n){
    if(check[n] == n){
        return n;
    }
    return check[n] = Find(check[n]);
}
int main(){
    fastio;
    cin>>N;
    for(int i=1; i<=N; i++){
        int x, y, z; cin>>x>>y>>z;
        xv.push_back(make_pair(x,i));
        yv.push_back(make_pair(y,i));
        zv.push_back(make_pair(z,i));
    }
    for(int i=1; i<=N; i++)
        check[i] = i;
    sort(xv.begin(), xv.end());
    sort(yv.begin(), yv.end());
    sort(zv.begin(), zv.end());
    for(int i=0; i<N-1; i++){
        edges.push_back(make_pair(xv[i+1].first - xv[i].first, make_pair(xv[i].second,xv[i+1].second)));
        edges.push_back(make_pair(yv[i+1].first - yv[i].first, make_pair(yv[i].second,yv[i+1].second)));
        edges.push_back(make_pair(zv[i+1].first - zv[i].first, make_pair(zv[i].second,zv[i+1].second)));
    }
    sort(edges.begin(),edges.end());
    for(int i=0; i<edges.size(); i++){
        int c1 = edges[i].second.first, c2 = edges[i].second.second;
        int p1 = Find(c1), p2 = Find(c2);
        if(p1 != p2){
            check[p1] = min(p1,p2);
            check[p2] = min(p1,p2);
            ans += edges[i].first;
        }
    }
    cout<<ans;
}