[백준] 2887번: 행성 터널 | C++

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

2887번: 행성 터널

 
 
 

접근방법

1. MST문제다. union-find 써야 할 것
2. 모든 행성 간 가중치를 구하려면 N! 인데?
3. 행성 간 가중치는 행성 간 3차원 거리가 아니라 min(|xA-xB|, |yA-yB|, |zA-zB|) 이다.
4. x, y, z 대로 정렬 3번 수행하고 인접한 행성의 거리를 구한다.
5. 힙에 넣어 가중치 최솟값을 구한다면?
라고 생각회로 거쳤다.
 
정렬 3번에, 우선순위 큐 사용에 유니온파인드면 시간초과 나는 거 아닌가? 생각했다. 그래도 딱히 다른 방법이 생각나지 않아 일단 위 아이디어로 구현했다. 근데 통과됐다. 결국 O(N^2logN)니까 시간초과 나지 않는 것 같다.
 
통과될지 모르고 러프하게 짠 코드라 튜플 덕지덕지.. 더 최적화를 하자면 X, Y, Z 배열 따로 나눠 관리하면 더 깔끔할 듯.

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<queue>
#define MAX 100000
#define fse(A,B,C) for(int i=A;i<B;i+=C)
using namespace std;
vector<tuple<int,int,int,int>> planet;
int parent[MAX];
int find(int x){
    if(parent[x]!=x) return find(parent[x]);
    return parent[x];
}
void makeunion(int a,int b){
    int x=find(a);
    int y=find(b);
    if(x<y) parent[x]=y;
    else parent[y]=x;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int N;
    cin>>N;
    fse(0,N,1){
        int x,y,z;
        cin>>x>>y>>z;
        planet.push_back({x,y,z,i});
    }
    sort(planet.begin(), planet.end(), [](tuple<int,int,int,int> a,tuple<int,int,int,int> b)-> bool {return get<0>(a) < get<0>(b);});
    priority_queue<tuple<int,int,int>> q;
    for(int i(1);i<N;i++) q.push({-abs(get<0>(planet[i-1])-get<0>(planet[i])), get<3>(planet[i-1]), get<3>(planet[i])});

    sort(planet.begin(), planet.end(), [](tuple<int,int,int,int> a,tuple<int,int,int,int> b)-> bool {return get<1>(a) < get<1>(b);});
    for(int i(1);i<N;i++) q.push({-abs(get<1>(planet[i-1])-get<1>(planet[i])), get<3>(planet[i-1]), get<3>(planet[i])});

    sort(planet.begin(), planet.end(), [](tuple<int,int,int,int> a,tuple<int,int,int,int> b)-> bool {return get<2>(a) < get<2>(b);});
    for(int i(1);i<N;i++) q.push({-abs(get<2>(planet[i-1])-get<2>(planet[i])), get<3>(planet[i-1]), get<3>(planet[i])});

    int answer=0;
    int K=N-1;
    for(int i(0);i<N;i++) parent[i]=i;
    while(K){
        auto top=q.top();
        q.pop();
        int x=get<1>(top), y=get<2>(top);
        if(find(x)==find(y)) continue;
        
        makeunion(x,y);
        answer+=-get<0>(top);
        K--;
    }
    cout<<answer;
}