[백준 2887] 행성 터널

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

2887번: 행성 터널

1/6일날 풀었떤 문제

요구사항

1. 모든 행성을 최소의 비용으로 연결(MST)

 

풀이

최소 스패닝 트리 문제이다.

거리는 x, y, z간의 거리 중 제일 최소의 거리이다. 다른 차원의 좌표가 거리에 영향을 끼치지 않는다

3. x, y, z각 각의 거리를 구한 후, 오름차순으로 정렬한다

4. Union-Find로 연결

 

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>
#include <vector>

using namespace std;
struct p{
    int x,y,z,num;
};

bool cmpx(p a, p b){
    return a.x>b.x;
}
bool cmpy(p a, p b){
    return a.y>b.y;
}
bool cmpz(p a, p b){
    return a.z>b.z;
}

p pl[1000000];

struct edge{
    int weight,from,to;
};

bool cmp(edge a, edge b){
    return a.weight>b.weight;
}

vector <edge> ed;

int parent[100000];

int Find(int x)
{
    if(parent[x]==x) return x;
    return parent[x]=Find(parent[x]);
}
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    parent[x]=y;
}
int n;
int main(){
    cin>>n;
    for(int i=0 ; i < n ; i++){
        scanf("%d%d%d",&pl[i].x, &pl[i].y,&pl[i].z);
        pl[i].num=i;
        parent[i]=i;
    }

    sort(pl,pl+n,cmpx);
    for(int i=0 ; i < n-1 ; i++){
        ed.push_back({abs(pl[i].x- pl[i+1].x), pl[i].num, pl[i+1].num});
    }
    sort(pl,pl+n,cmpy);
    for(int i=0 ; i < n-1 ; i++){
        ed.push_back({abs(pl[i].y- pl[i+1].y), pl[i].num, pl[i+1].num});
    }
    sort(pl,pl+n,cmpz);
    for(int i=0 ; i < n-1 ; i++){
        ed.push_back({abs(pl[i].z- pl[i+1].z), pl[i].num, pl[i+1].num});
    }

    sort(ed.begin(),ed.end(),cmp);

    int ans=0;
    int cnt=0;
    for(int i = ed.size()-1; cnt!=n-1; i--){
        if(Find(ed[i].from) != Find(ed[i].to)){
            cnt++;
            ans+=ed[i].weight;
            Union(ed[i].from, ed[i].to);
        }
        if(cnt==n-1)
            break;
    }
    printf("%d",ans);
    return 0;
}