[BOJ2887] 행성 터널

 

어떻게 진행해야 할까?

이 문제는 정렬이 있는 것으로 보아 각 점에 대해서 정렬해야 해답이 볼 수 있는 건 당연하다.

 

알고리즘 분류에서는 정렬 뿐만 아닌 MST(최소 스패닝 트리)가 있다.

MST는 최소의 비용을 산출하기 위한 알고리즘이며,

이 문제는 최소 비용을 구하는 프로그램이 주된 목적이므로,

 

정렬을 먼저 한 다음, MST를 활용한다면 아무런 문제 없이 풀 수 있다.

물론, MST는 처음 들어 보신 분이라면 난감할 수 있다고 생각한다.

 

최소 스패닝 트리는 무엇일까?

어떤 정점과 다른 정점 사이의 비용을 가지고, find와 merge를 이용하여 최소 비용을 찾아내는 방식이다.

이 설명이 맞는지 모르겠지만, geeksforgeeks에서 검색해보면 더 자세한 설명이 나와 있을 것이다.

 

정렬 기준은 x, y, z 그리고, cost도 정렬해야 한다.

그래야 최소 스패닝 트리 작업을 재빨리 마무리하고 칼퇴가 가능하다. (ㅋㅋㅋ)

 

소스는 참고용으로 쓰길 바란다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct planet
{
    int x, y, z, idx;
};

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

int parent[100001];
vector<planet> p;
vector<edge> e;

bool cmpX(planet a, planet b)
{
    return a.x < b.x;
}

bool cmpY(planet a, planet b)
{
    return a.y < b.y;
}

bool cmpZ(planet a, planet b)
{
    return a.z < b.z;
}

bool cmpCost(edge a, edge b)
{
    return a.cost < b.cost;
}

int find(int x)
{
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return;
    parent[y] = x;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        planet tmp;
        cin >> tmp.x >> tmp.y >> tmp.z;
        tmp.idx = i;
        p.push_back(tmp);
    }
    sort(p.begin(), p.end(), cmpX);
    for(int i = 0; i < n-1; i++)
    {
        edge tmp;
        tmp.from = p[i].idx;
        tmp.to = p[i+1].idx;
        tmp.cost = abs(p[i].x - p[i+1].x);
        e.push_back(tmp);
    }
    sort(p.begin(), p.end(), cmpY);
    for(int i = 0; i < n-1; i++)
    {
        edge tmp;
        tmp.from = p[i].idx;
        tmp.to = p[i+1].idx;
        tmp.cost = abs(p[i].y - p[i+1].y);
        e.push_back(tmp);
    }
    sort(p.begin(), p.end(), cmpZ);
    for(int i = 0; i < n-1; i++)
    {
        edge tmp;
        tmp.from = p[i].idx;
        tmp.to = p[i+1].idx;
        tmp.cost = abs(p[i].z - p[i+1].z);
        e.push_back(tmp);
    }
    sort(e.begin(), e.end(), cmpCost);
    for(int i = 0; i < n; i++)
        parent[i] = i;
    int ans = 0;
    for(int i = 0; i < e.size(); i++)
    {
        if(find(e[i].from) != find(e[i].to))
        {
            merge(e[i].from, e[i].to);
            ans += e[i].cost;
        }
    }
    cout << ans;
    return 0;
}

기네.

ㅋㅋㅋㅋ