[BOJ 2887] 행성터널

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

모든 행성이 연결되는 MST를 만드는 문제이다. 하지만 보통 구하느 MST와는 다르게 N의 제한이 10만이기 때문에 모든 간선의 길이를 다 넣어주게 되면 O(N^2)으로 시간초과&메모리 초과 콤비를 맞게 될 것이다. 

따라서 간선을 넣어줄 때 필요한 부분만 넣어주는 처리가 필요하다. 

핵심은 거리가 Min(x절대값 차이, y절대값 차이, z절대값 차이) 이므로 각각 x,y,z를 기준으로 sort해준 다음 인전한 경우에만 거리를 넣어주는 3N의 시간복잡도를 넣어주게 되면 해결할 수 있다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <stdio.h>
 
#define INF 1e9
typedef long long ll;
using namespace std;
 
int n,parent[111111];
 
vector<pair<int,int>> v1;
vector<pair<int,int>> v2;
vector<pair<int,int>> v3;
 
vector<pair<int,pair<int,int>>> vt;
 
int find(int x){
    if(x == parent[x]){
        return x;
    }else{
        return parent[x] = find(parent[x]);
    }
}
void merge(int x, int y){
    x = find(x);
    y = find(y);
    parent[x] = y;
}
void init(){
    for(int i=0;i<=n;i++){
        parent[i] = i;
    }
}
 
int main(){
    cin >>n;
    for(int i=1;i<=n;i++){
        int a,b,c;
        cin>> a >>b >>c;
        v1.push_back({a,i});
        v2.push_back({b,i});
        v3.push_back({c,i});
    }
    
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    sort(v3.begin(),v3.end());
    
    for(int i=0;i<v1.size()-1;i++){
        vt.push_back({(abs)(v1[i].first-v1[i+1].first),{v1[i].second,v1[i+1].second}});
        vt.push_back({(abs)(v2[i].first-v2[i+1].first),{v2[i].second,v2[i+1].second}});
        vt.push_back({(abs)(v3[i].first-v3[i+1].first),{v3[i].second,v3[i+1].second}});
    }
    init();
    sort(vt.begin(),vt.end());
    
    int ans = 0;
    for(int i=0;i<vt.size();i++){
        auto p = vt[i];
        int x = find(p.second.first);
        int y = find(p.second.second);
        
        if(x!= y){
            merge(x,y);
            ans += p.first;
        }
    }
    cout <<ans <<endl;
 
    return 0;
}