백준 2887 행성 터널 (C++)

2887번: 행성 터널

최소 스패닝 트리를 이용한 문제이다. 문제 유형은 최소 스패닝 트리로 되어 있지만 사실상 크루스칼 알고리즘에서 사용할 경로와 가중치를 구하는 부분이 생각해내는데 시간이 오래 걸린다. 기존 크루스칼 알고리즘을 사용을 하는데 주어진 좌표들을 이용해 경로와 가중치를 구해주어야 한다. 그러나 단순 반복문으로 좌표 간의 거리를 모두 구하게 된다면 이는 O(N^2)가 되고 N의 최댓값이 100,000이므로 메모리 초과가 발생하게 된다. 그렇기에 모든 경로가 아닌 가능성이 있는 경로만을 구해야 한다. 우선 주어지는 좌표에서 x, y, z 좌표를 각각의 벡터에 저장을 해준다. 그리고 모두 오름차순으로 정렬을 해준 뒤 N 만큼 반복문을 돌려주며 각 좌표 간의 거리를 구해 v에 저장을 해준다. 이렇게 해주는 이유는 문제에서 말하는 거리 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|) 인데 결국 좌표 x,y,z들중 하나의 값만 사용하게 된다. 그렇기에 좌표 x,y,z 각각의 최소 거리를 구해 크루스칼 알고리즘을 돌려주게 되면 최소값을 구할 수 있다. 이 후는 크루스칼 알고리즘을 통해 결과를 구하고 출력해주었다.
생각보다 까다로웠던 문제였다. 크루스칼 알고리즘을 사용한다는 점은 바로 떠올릴 수 있었는데 이를 사용하기 위해 주어진 값을 어떻게 가공해야할지 아이디어가 잘 떠오르지 않았다. 문제에 주어진 거리를 구하는 공식을 보고 아이디어를 떠올릴 수 있었다. 최소 스패닝 트리의 이러한 방식도 기억해두어야 겠다.

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

using namespace std;

int N, result = 0;
vector<pair<int, pair<int, int>>> v;
vector<pair<int, int>> x;
vector<pair<int, int>> y;
vector<pair<int, int>> z;
int p[100000];

int findParent(int a) {
    if (a == p[a]) return a;
    else return p[a] = findParent(p[a]);
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a != b) p[a] = b;
}

bool sameParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a == b) return true;
    else return false;
}

void findRoute() {
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    sort(z.begin(), z.end());

    for (int i = 0; i < N - 1; i++) {
        v.push_back({ abs(x[i].first - x[i + 1].first),{x[i].second, x[i + 1].second} });
        v.push_back({ abs(y[i].first - y[i + 1].first),{y[i].second, y[i + 1].second} });
        v.push_back({ abs(z[i].first - z[i + 1].first),{z[i].second, z[i + 1].second} });
    }
}

void solution() {
    findRoute();

    sort(v.begin(), v.end());

    for (int i = 0; i < N; i++) {
        p[i] = i;
    }

    for (int i = 0; i < v.size(); i++) {
        int a = v[i].second.first;
        int b = v[i].second.second;
        int c = v[i].first;

        if (!sameParent(a, b)) {
            unionParent(a, b);
            result += c;
        }
    }

    cout << result;
}

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

    cin >> N;

    int a, b, c;
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c;
        x.push_back({ a,i });
        y.push_back({ b,i });
        z.push_back({ c,i });
    }

    solution();

    return 0;
}