[백준] 2887: 행성 터널

0. 문제 주소

 

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

2887번: 행성 터널

 

 

1. 풀이

 

1. 모든 행성 연결, 2. 최소 비용 -> MST이다.

 

여기서 N이 10만이므로, 모든 간선을 다 고려한다면 당연하게도 터진다.

 

행성과 행성을 연결하는 비용의 정의는 다음과 같다고 한다.

 

 

두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

 

행성 A와 B를 연결할 때는, x, y, z 좌표 차이 중 가장 작은 값만 택하여, 그것을 간선의 가중치로 만들어주면 된다.

 

우리는 크루스칼 알고리즘을 적용시킬 때, PQ에 넣어줄 간선을 최소화하는 것이 목적이다.

 

x좌표에 대해, y좌표에 대해, z좌표에 대해 모든 행성들을 정렬시켜 주고,

 

그 순서에서 인접한 행성들 끼리만 간선을 이어 준다.

 

이렇게 하고 모든 간선들을 PQ(min heap)에 넣어주면, 가중치가 가장 작은 간선이 먼저 뽑히게 된다.

 

터널로 연결할 때의 비용의 정의가 min(|xA-xB|, |yA-yB|, |zA-zB|) 이어도, PQ에서 나오게 되는 간선은 이미

 

x, y, z 좌표의 차이 중 가장 작은 값을 가중치로 가지는 간선이기 때문에, 모든 간선을 넣어주지 않아도

 

비용의 정의에 알맞게 모든 간선을 이어줄 수 있다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define pii pair<int, int>
#define piii pair<int, pii>
#define MAX 100005

using namespace std;


typedef struct Planet{
    int num;
    int x;
    int y;
    int z;
    
}P;

bool cmpx(const P &A, const P &B){
    return A.x < B.x;
}

bool cmpy(const P &A, const P &B){
    return A.y < B.y;
}

bool cmpz(const P &A, const P &B){
    return A.z < B.z;
}

int N;
int p[MAX];
P planets[MAX];
priority_queue<piii, vector<piii>, greater<piii>> PQ;

int find(int a){
    if (p[a] == -1) return a;
    
    return p[a] = find(p[a]);
}

bool merge(int a, int b){
    int roota = find(a);
    int rootb = find(b);
    if (roota == rootb) return false;
    
    p[roota] = rootb;
    return true;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    memset(p, -1, sizeof(p));
    scanf("%d", &N);
    for (int i=0;i<N;i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        P temp;
        temp.num = i, temp.x = x, temp.y = y, temp.z = z;
        planets[i] = temp;
    }
    
    sort(planets, planets+N, cmpx);
    for (int i=0;i<N-1;i++){
        P A = planets[i];
        P B = planets[i+1];
        PQ.push(make_pair(abs(A.x - B.x) , pii(A.num, B.num)));
    }

    sort(planets, planets+N, cmpy);
    for (int i=0;i<N-1;i++){
        P A = planets[i];
        P B = planets[i+1];
        PQ.push(make_pair(abs(A.y - B.y) , pii(A.num, B.num)));
    }

    sort(planets, planets+N, cmpz);
    for (int i=0;i<N-1;i++){
        P A = planets[i];
        P B = planets[i+1];
        PQ.push(make_pair(abs(A.z - B.z) , pii(A.num, B.num)));
    }        
    
    int edge_cnt = 0;
    int ans = 0;
    while (edge_cnt < N-1){
        auto pp = PQ.top();
        PQ.pop();
        int w = pp.first;
        int a = pp.second.first, b = pp.second.second;
        if (merge(a, b)) {
            edge_cnt++;
            ans += w;
        }
    }
    
    printf("%d\n", ans);
    
    return 0;
}