행성 터널


작성일 : 2017-01-16 20:08:36
조회수 : 745



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


3차원 좌표가 주어져 있고, 두 행성간 터널을 연결할 때 드는 비용은 x,y,z 좌표 중 차이가 최소가 되는 경우라고 하였으므로, 모든 행성간의 x,y,z에 대해 한 번씩 정렬한 후, 정렬된 행성을 $i$번째와 $i-1$번째 행성과 연결하여 후보군에 집어 넣습니다.


이렇게 각 좌표에 대해 최솟값 연결 후보군을 집어 넣은 다음, 최소 스패닝 알고리즘을 이용하여 모든 행성에 대해 연결시켜주면 됩니다. 소스코드에서는 크루스칼 알고리즘을 사용하였습니다.

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

class Node
{
public:
    int no, x, y, z;
    Node() {}
    Node(int no, int x, int y, int z) : no(no), x(x), y(y), z(z) {}
};
class Edge
{
public:
    int src, dest, cost;
    Edge() {}
    Edge(int a, int b, int c) : src(a), dest(b), cost(c) {}
    bool operator <(const Edge &n)
    {
        return cost < n.cost;
    }
};
bool cmp(Node a, Node b)
{
    return a.x < b.x;
}
bool cmp2(Node a, Node b)
{
    return a.y < b.y;
}
bool cmp3(Node a, Node b)
{
    return a.z < b.z;
}
int par[100001];
int find(int x)
{
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y)
{
    par[find(y)] = find(x);
}
int main()
{
    ios::sync_with_stdio(false);

    int n;
    long long ans=0;
    vector<Node> vn;
    vector<Edge> chk;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a, b, c;

        cin >> a >> b >> c;
        vn.push_back({ i+1,a,b,c });
    }
    sort(vn.begin(), vn.end(), cmp);
    for (int i = 1; i < n; i++)
        chk.push_back({ vn[i].no,vn[i-1].no,abs(vn[i].x - vn[i - 1].x) });
    sort(vn.begin(), vn.end(), cmp2);
    for (int i = 1; i < n; i++)
        chk.push_back({ vn[i].no,vn[i-1].no,abs(vn[i].y - vn[i - 1].y) });
    sort(vn.begin(), vn.end(), cmp3);
    for (int i = 1; i < n; i++)
        chk.push_back({ vn[i].no,vn[i-1].no,abs(vn[i].z - vn[i - 1].z) });
    for (int i = 1; i <= n; i++) par[i] = i;
    sort(chk.begin(), chk.end());
    for (int i = 0; i < chk.size(); i++)
    {
        int l = find(chk[i].src), r = find(chk[i].dest);
        if (l != r)
        {
            merge(l, r);
            ans += chk[i].cost;
        }
    }
    cout << ans;
}

행성 터널 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글