백준 2887번 행성 터널[C++]

1. 문제 풀이

 문제의 유형은 최소 신장 트리입니다. 행성을 잇는 통로 N - 1개를 설치하는 비용의 최소를 구해야 합니다. 행성은 3차원 좌표 위에 한 점으로 표기가 되고 두 행성 A(ax, ay, az)와 B(bx, by, bz) 사이의 통로 설치 비용은 min( |ax - bx|, |ay - by|, |az - bz|)입니다.

 

< naive 한 풀이 방법 >

 행성을 잇는 모든 통로의 비용을 계산한 다음 MST를 수행하여 최소 비용을 구하는 방법이 있습니다.

 

N개의 행성에 대해서 모든 통로의 개수는 N(N-1) / 2 개입니다. N은 조건에서 최대 100,000까지 주어질 수 있으므로 모든 통로의 비용을 구하는 로직의 시간복잡도는 O(N^2)가 되어 TLE를 받을 수 있습니다. N이 적었더라면 고려해볼만한 풀이인데 백준 1774번 우주신과의 교감에서 사용하는 방법입니다.

 

 그렇다면 통로의 비용을 구하는 방법을 다시 생각해봐야 합니다. 통로의 비용을 계산하는 식을 다시 가져와서 보면  min( |ax - bx|, |ay - by|, |az - bz|)입니다. 이는 x, y, z 좌표값에 대해서 독립적입니다. 즉 x, y, z를 따로 저장해 정렬하여 통로 비용을 계산하면 O(N log N + 3N)으로 개선이 가능합니다. ( 이러한 로직이 가능한 이유엔 복잡한 증명식이 있었습니다 )

 

 각 축에 대해서 통로 비용을 계산해서 저장해 정렬한 다음 MST를 구해주었습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

vi p(100'005, -1);

int find(int x) { return (p[x] < 0 ? x : p[x] = find(p[x])); }

int merge(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) return 0;

    if(p[x] == p[y]) p[x]--;
    if(p[x] > p[y]) swap(x, y);
    p[y] = x;
    return 1;
}

int n;
vpl xpos, ypos, zpos;

int main() {
    fastio(nullptr, false);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        ll x, y, z;
        cin >> x >> y >> z;
        xpos.pb({x, i});
        ypos.pb({y, i});
        zpos.pb({z, i});
    }

    sort(all(xpos));
    sort(all(ypos));
    sort(all(zpos));

    vtl edges;
    for(int i = 0; i < n - 1; i++) {
        edges.pb({abs(xpos[i].X - xpos[i+1].X), xpos[i].Y, xpos[i+1].Y});
        edges.pb({abs(ypos[i].X - ypos[i+1].X), ypos[i].Y, ypos[i+1].Y});
        edges.pb({abs(zpos[i].X - zpos[i+1].X), zpos[i].Y, zpos[i+1].Y});
    }

    sort(all(edges));
    
    int cnt{};
    ll ans{};
    for(auto &[cost, x, y] : edges) {
        if(!merge(x, y)) continue;
        cnt++;
        ans += cost;
        if(cnt == n - 1) break;
    }

    cout << ans;
}

 

3. 제출 결과