행성 터널

MST에서 사용하는 kruskal알고리즘을 쓰면 풀리는 문제이다.

kruskal에 대해 간단하게 설명하자면, 간선들을 가중치 순으로 오름차순 정렬하고

앞에서부터 간선을 보고 둘이 이어져 있지 않다면 잇고 이미 이어져 있으면 잇지 않는 시행을 반복해서

이은 간선이 N-1개가 되면 멈추는 알고리즘이다.

이어져 있는지 아닌지는 union-find로 판단한다.

매우 간단한 알고리즘인데 이 문제에서는 한가지 더 생각을 해야 한다.

간선이 N^2개이기 때문에 모두 넣을 수가 없다.

따라서 x,y,z 각각을 오름차순 정렬을 한 다음에 이웃한 것끼리의 간선만 저장하는 식으로 하면 3(N-1)개의 간선을 가지고 

kruskal 알고리즘을 돌리면 된다.

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
pair<int,long long> tunnel_x[100004],tunnel_y[100004],tunnel_z[100004];
int N;
int parent[100004];
struct Data{
    int a,b;
    long long dist;
    bool operator<(const Data r)const{
        return dist>r.dist;
    }
};
priority_queue<Data>lines;
int finds(int a)
{
    if(parent[a]==a) return a;
    return parent[a]=finds(parent[a]);
}
void unions(int a,int b)
{
    if(parent[finds(a)]!=parent[finds(b)])
    {
        parent[finds(a)]=parent[finds(b)];
    }
}
long long kruskal()
{
    sort(tunnel_x+1,tunnel_x+N+1);
    sort(tunnel_y+1,tunnel_y+N+1);
    sort(tunnel_z+1,tunnel_z+N+1);
    for(int i=1;i<=N-1;i++)
    {
        lines.push({tunnel_x[i].second,tunnel_x[i+1].second,abs(tunnel_x[i].first-tunnel_x[i+1].first)});
        lines.push({tunnel_y[i].second,tunnel_y[i+1].second,abs(tunnel_y[i].first-tunnel_y[i+1].first)});
        lines.push({tunnel_z[i].second,tunnel_z[i+1].second,abs(tunnel_z[i].first-tunnel_z[i+1].first)});
    }
    long long cnt=0,ans=0;
    while(cnt<N-1)
    {
        Data t = lines.top();
        lines.pop();
        if(finds(t.a)!=finds(t.b))
        {
            unions(t.a,t.b);
            ans+=t.dist;
            cnt++;
        }
    }
    return ans;
}
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
    {
        long long x,y,z;
        scanf("%lld %lld %lld",&x,&y,&z);
        tunnel_x[i]=make_pair(x,i);
        tunnel_y[i]=make_pair(y,i);
        tunnel_z[i]=make_pair(z,i);
        parent[i]=i;
    }
    printf("%lld",kruskal());
}

해결 코드이다.