[C++/2887] 행성 터널 - using MST : Kruskal Algorithm

문제

 

아이디어: 최소 비용으로 그래프를 완성하는 전형적인 MST 문제이다. Kruskal 알고리즘을 사용하였다.

여기서 중요한 점은 간선 정보를 입력받은 후, 간선의 비용은 직접 abs와 min으로 직접 구해야한다는 것이다.

 

풀이:

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int parent[100000];

int findParent(int x)
{
    return (parent[x] == x ? x : parent[x] = findParent(parent[x]));
}

void unionParent(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
    
    if (a < b)
        parent[b] = a;
    else
        parent[a] = b;
}

int main()
{
    // N(행성 개수)
    int N;
    cin>>N;
    
    // {행성 번호, {x, y, z 좌표}}
    vector<pair<int, tuple<int, int, int>>> q;
    // {cost, {node1, node2}}
    vector<pair<int, pair<int, int>>> v;
    
    for(int i = 0;i < N;i++)
    {
        int x, y, z;
        cin>>x>>y>>z;
        
        q.push_back({i, {x, y, z}});
    }
    
    for(int i = 0;i < q.size();i++)
    {
        int num = q[i].first;

        int x = get<0>(q[i].second);
        int y = get<1>(q[i].second);
        int z = get<2>(q[i].second);
        
        for(int j = i + 1;j < q.size();j++)
        {
            int num2 = q[j].first;

            int x2 = get<0>(q[j].second);
            int y2 = get<1>(q[j].second);
            int z2 = get<2>(q[j].second);

            v.push_back({min(abs(x2 - x), min(abs(y2 - y), abs(z2 - z))), {num, num2}});
        }
    }
    
    for(int i = 0;i < N;i++)
        parent[i] = i;
    
    sort(v.begin(), v.end());
    
    int result = 0;
    for(int i = 0;i < v.size();i++)
    {
        int cost = v[i].first;
        
        int a = v[i].second.first;
        int b = v[i].second.second;
        
        if (findParent(a) != findParent(b))
        {
            unionParent(a, b);
            result += cost;
        }
    }
    
    cout<<result<<endl;
    
    return 0;
}