BOJ 2887 : 행성 터널

풀이 상세

MST 알고리즘

풀이 요약

1. 임의의 노드 $x_1, y_1, z_2$ 와 $x_2, y_2, z_2$ 를 비교하여 가장 짧은 경로를 찾아 이어 가야 한다.

2. 이 문제는 $dist$ 의 차이가 있을 뿐, 모든 노드끼리 이어질 가능성이 있다는 것이다. 이러한 행성간 모든 간선을 찾아 탐색하는 경우는, int 를 사용해도, 10만 10만-1 4bytes 이므로 어마어마한 메모리 초과가 발생하게 된다. 따라서 최소 스패닝 트리의 특성을 이용하여, 탐색해야 하는 값을 줄이는 것이 관건이다.

3. 탐색 값을 줄이는 과정은 다음과 같다. (구글 참조)

   • 결국 우리는 x, y, z 비교 중 가장 작은 경로를 찾는다.
   • 백터를 3개로 나누어, x 끼리, y 끼리, z 끼리 정보를 담은 후, 먼저 1차 정렬을 한다.
   • 만약 임의의 노드 $A$ 와 노드 $B$ 가 존재하는데 있어 $x$ 로 이어지는 것이 가장 짧은 경로라로 한다면, 1차 정렬에서 $x$ 백터의 노드 $A$ 인덱스를 $vx$ 라 했을 때, 노드 $B$ 의 인덱스는 $vx+1$ 혹은 $vx-1$ 이 된다. 즉 백터간 서로 인접한 인덱스끼리가 해당 좌표에서 가장 짧은 경로로 만날 수 있는 경우이다.
   • 이를 $x$ , $y$ , $z$ 백터로 모두 확인하여, 그 가운데 나오는 최종적으로 가장 짧은 경로들을 $pq$ 에 담는다. 이렇게 하면 $3N$ 만큼의 간선만 $pq$ 에 담아 최소 스패닝 트리를 찾는 것이 가능하다.

배운점

• PQ 의 정렬은 기본적으로 내림차순이다. 오름차순을 원한다면 cmp 함수를 만들어야 하나, 단순한 int 기반의 정렬이라면 정렬 기준에 -1을 곱하는 것으로 함수를 만들지 않아도 오름차순을 하는 것이 가능하다.

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

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;

const int N_MAX = 1e6 + 4;
int N, p[N_MAX], cnt;
priority_queue<pii> pq;
vector<pi> arr[3];
ll result;

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

bool setUnion(int n1, int n2) {
    int p1 = findParent(n1);
    int p2 = findParent(n2);
    if (p1 == p2) return false;
    p[p1] = p2;
    cnt++;
    return true;
}

void solve() {
    while (cnt < N - 1) {
        pii curr = pq.top();
        pq.pop();
        if (setUnion(curr.second.first, curr.second.second))
            result += curr.first*-1;
    }
}

void output() {
    cout << result;
}

void input() {
    cin >> N;
    int x, y, z;
    for (int i = 0; i < N; i++) p[i] = i;

    for (int i = 0; i < N; i++) {
        cin >> x >> y >> z;
        arr[0].push_back({x, i});
        arr[1].push_back({y, i});
        arr[2].push_back({z, i});
    };

    sort(arr[0].begin(), arr[0].end());
    sort(arr[1].begin(), arr[1].end());
    sort(arr[2].begin(), arr[2].end());

    for (int i = 0; i < N-1; i++) {
        pq.push({arr[0][i].first - arr[0][i + 1].first, {arr[0][i].second, arr[0][i + 1].second}});
        pq.push({arr[1][i].first - arr[1][i + 1].first, {arr[1][i].second, arr[1][i + 1].second}});
        pq.push({arr[2][i].first - arr[2][i + 1].first, {arr[2][i].second, arr[2][i + 1].second}});
    }
}

int main() {
    input();
    solve();
    output();
}