[BOJ 2887] 행성 터널

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

2887번: 행성 터널

#include <bits/stdc++.h>

using namespace std;
int parent[100000];

class Edge{
    public:
    int a;
    int b;
    long cost;
    Edge(int a, int b, long cost){
        this->a=a;
        this->b=b;
        this->cost=cost;
    }
};

bool sortX(const pair<int, vector<int> >&v1, const pair<int, vector<int> > &v2){
    return v1.second[0]<v2.second[0];
}

bool sortY(const pair<int, vector<int> >&v1, const pair<int, vector<int> > &v2){
    return v1.second[1]<v2.second[1];
}

bool sortZ(const pair<int, vector<int> >&v1, const pair<int, vector<int> > &v2){
    return v1.second[2]<v2.second[2];
}

struct cmp{                 //Minheap을 위한 비교자
    bool operator()(const Edge &a, const Edge &b){    
        return a.cost>b.cost;
    }
};

int find(int a){
    if (parent[a]==a){
        return a;
    }
    else{
        return parent[a]=find(parent[a]);
    }
}

void union_(int a, int b){
    int pa=find(a);
    int pb=find(b);
    parent[pa]=pb;
}

int main(){
    int N;
    int x,y,z;
    long sum=0;
    int connected=0;
    cin>>N;
    vector<pair<int, vector<int> > > v;     //first: 행성 번호 second: 행성 위치
    priority_queue<Edge, vector<Edge>, cmp> pq;
    for (int i=0; i<N; i++){
        vector<int> temp;
        parent[i]=i;
        cin>>x>>y>>z;
        temp.push_back(x); temp.push_back(y); temp.push_back(z);
        v.push_back(make_pair(i, temp));
    }
    sort(v.begin(), v.end(), sortX);
    for (int i=0; i<N-1; i++){
        pq.push(Edge(v[i].first, v[i+1].first, labs(v[i].second[0]-v[i+1].second[0])));
    }
    sort(v.begin(), v.end(), sortY);
    for (int i=0; i<N-1; i++){
        pq.push(Edge(v[i].first, v[i+1].first, labs(v[i].second[1]-v[i+1].second[1])));
    }
    sort(v.begin(), v.end(), sortZ);
    for (int i=0; i<N-1; i++){
        pq.push(Edge(v[i].first, v[i+1].first, labs(v[i].second[2]-v[i+1].second[2])));
    }
    while (!pq.empty()){
        Edge e=pq.top();
        pq.pop();
        if (connected==N-1){
            break;
        }
        if (find(e.a)!=find(e.b)){
            union_(e.a, e.b);
            sum+=e.cost;
            connected+=1;
        }
    }
    cout<<sum<<"\n";
    return 0;
}

코드가 엄청 길다..

자료구조를 한꺼번에 때려박는(??) 바람에..

 

MST(Minimum Spanning Tree)+정렬을 결합한 문제였다.

 

처음에는 접근을 한 정점과 나머지 모든 정점의 거리를 구해서 크루스칼을 돌리는 방식이었는데 이렇게 하면 시간초과가 발생한다. 거리를 구하는 것만으로도 시간복잡도 O(N^2) 가 걸린다.

 

잘 생각해보면 "최소의 비용" 으로 모든 정점을 잇는 것이므로, 이웃한 정점 끼리의 거리(간선)만 고려해 주면 된다.

여기서 이웃한 정점이란 x축, y축, z축 측면에서 서로 가장 가까운 정점을 의미한다.

 

x축, y축, z축 기준으로 행성의 좌표를 정렬해준다. 

정렬한 후 서로 이웃한 정점 간의 비용을 구해서 Edge 구조체(정점 a, 정점 b, 비용)를 priority queue에 넣어준다. 이 priority queue는 minheap 이다. 이렇게 구성한 후 크루스칼을 돌린다. 모든 간선은 cost 오름차순 정렬되어있고, 간선 뽑았을 때 서로 연결(find(a)==find(b)) 되어 있으면 아무것도 하지 않고 서로 연결되어있지 않으면 union 으로 연결해준다. 

이후 연결된 정점이 N-1개면 반복문을 빠져나와 결과를 출력한다.

 

이 문제의 포인트는 위치를 정렬해서 거리적으로 이웃한 정점끼리의 간선만 고려(최소 비용을 구하는 것과 깊은 연관) 하고 이 간선에 대해서 MST를 만들어주면 되는 것이다.

 

(자료구조를 x,y,z축 서로 분리해서 해주는게 가독성이 훨 좋고 간단한 방식인듯)