BOJ 백준 2887 : 행성 터널

시작하면서

　이번 문제는 최소 스패닝 트리(MST: Minimum Spanning Tree) 문제의 일부인 크루스칼 알고리즘(Kruskal’s Algorithm) 문제이다.

BOJ 2887 - 행성 터널

​

문제 이해

​ 이 문제는 크루스칼 알고리즘을 조금 변형해서 사용한 문제이다. 문제를 읽어보면 간선에 대한 정보는 없고, 각 점들의 정보만 있다. 만약 이 정점들을 모두 간선으로 만드려고 하면, 100,000개의 정점들을 각각 서로 연결해보아야 하고, x-y-z 좌표를 따로 계산해야하므로 3배로 계산을 해야한다.

​ 이를 등차수열로 계산해보면

Sn = (n * (2a + n(n-1)d) / 2)
Sn = 100,000 * (2*100,000 + 100,000 * 99,999 * 1) / 2

이와 같은 감당하지 못할 큰 수가 나오므로 시간 및 메모리 초과가 발생할 것이다.

​ 그러므로 최소의 길이만 가진 간선들을 만들어야 한다. 순서는 다음과 같다.

1. x, y, z 좌표끼리 나눈다.
2. 각 좌표를 내림차순으로 정렬한다.
3. 정렬한 좌표로 간선을 만든다.
4. 만들어진 x, y, z 간선들을 모두 합쳐서 크루스칼 알고리즘을 사용해 최소 신장 트리를 만든다.

​ 위 순서대로 문제를 해결하면 된다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

class Tunnel
{
public:
    int planet01Index, planet02Index;
    int weight;

    Tunnel(int i01, int i02, int w)
    {
        planet01Index = i01;
        planet02Index = i02;
        weight = w;
    }
};

bool _tunnel_compare(const Tunnel &a, const Tunnel &b)
{
    return a.weight < b.weight;
}

bool _pair_compare(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.second > b.second;
}

int GetRoot(vector<int>& rootVector, int index)
{
    if (rootVector[index] == index)
    {
        return index;
    }

    return rootVector[index] = GetRoot(rootVector, rootVector[index]);
}

int main()
{
    // sync off
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // sync off

    vector<pair<int, int>> planetX, planetY, planetZ;
    vector<Tunnel> tunnel;
    vector<int> rootVector;
    int N;

    cin >> N;

    planetX.resize(N);
    planetY.resize(N);
    planetZ.resize(N);
    for (int i = 0; i < N; i++)
    {
        planetX[i].first = i;
        planetY[i].first = i;
        planetZ[i].first = i;
        cin >> planetX[i].second >> planetY[i].second >> planetZ[i].second;
    }

    sort(planetX.begin(), planetX.end(), _pair_compare);
    sort(planetY.begin(), planetY.end(), _pair_compare);
    sort(planetZ.begin(), planetZ.end(), _pair_compare);

    for (int i = 0; i < N - 1; i++)
    {
        Tunnel xTunnel(planetX[i].first, planetX[i + 1].first, planetX[i].second - planetX[i + 1].second);
        Tunnel yTunnel(planetY[i].first, planetY[i + 1].first, planetY[i].second - planetY[i + 1].second);
        Tunnel zTunnel(planetZ[i].first, planetZ[i + 1].first, planetZ[i].second - planetZ[i + 1].second);

        tunnel.push_back(xTunnel);
        tunnel.push_back(yTunnel);
        tunnel.push_back(zTunnel);
    }

    sort(tunnel.begin(), tunnel.end(), _tunnel_compare);

    rootVector.resize(N);
    for (int i = 0; i < rootVector.size(); i++)
    {
        rootVector[i] = i;
    }

    int tunnelWeightSum = 0;
    for (int i = 0; i < tunnel.size(); i++)
    {
        int planet01Index = tunnel[i].planet01Index;
        int planet02Index = tunnel[i].planet02Index;
        int weight = tunnel[i].weight;

        int root01 = GetRoot(rootVector, planet01Index);
        int root02 = GetRoot(rootVector, planet02Index);

        if (root01 == root02)
        {
            continue;
        }

        rootVector[root02] = root01;
        tunnelWeightSum += weight;
    }

    cout << tunnelWeightSum;

    return 0;
}