[BOJ] 백준 2887 행성 터널

문제 링크

www.acmicpc.net/problem/2887

2887번: 행성 터널

 

풀이

점이 10만 개입니다. 이론상 모든 점을 연결할 수 있으므로 완전 그래프 꼴이긴 합니다. 간선이 너무 많은 것만 빼면 전형적인 최소 스패닝 트리 문제입니다.

 

근데 잘 생각해보면 굳이 모든 간선을 볼 필요가 없습니다.

우리는 최소 스패닝 트리를 만들거니까 축별로 정렬 후 이웃한 점끼리만 간선을 맺어주면 됩니다.

 

이게 왜 되는지 그림으로 살펴봅시다.

어떤 한 축만 고려했을 때, $a, b, c$가 그림처럼 연속한 점이라고 하겠습니다.

 

 

최소 스패닝 트리를 만드는 과정에서 우선 $a$-$b$를 연결합니다.

 

다음으론 $b$-$c$를 연결합니다.

이렇게 되면 무슨일이 있어도 $a$와 $c$는 거리 3으로 연결되지 않습니다.

즉, 좌표순으로 이웃한 정점끼리의 간선만 고려해줘도 된다는 말입니다.

 

이 원리를 적용하면 결국 정점 하나당 최대 6개의 간선만 존재하게 됩니다.

적당한 크기의 그래프를 모델링했으니 최소 스패닝 트리를 쉽게 구할 수 있습니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

vpll p1, p2, p3;
int n;
int par[111'111];

int find(int x) {
    if (par[x] == -1) return x;
    return par[x] = find(par[x]);
}

struct Edge {
    int u, v;
    ll c;

    Edge(int u = 0, int v = 0, ll c = 0) : u(u), v(v), c(c) {}
};

vector<Edge> p;

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

    memset(par, -1, sizeof(par));
    cin >> n;
    for (int i = 0; i < n; i++) {
        ll x, y, z;
        cin >> x >> y >> z;
        p1.emplace_back(x, i);
        p2.emplace_back(y, i);
        p3.emplace_back(z, i);
    }
    sort(all(p1));
    sort(all(p2));
    sort(all(p3));

    auto foo = [&](pll a, pll b) {
        int u = a.sd, v = b.sd;
        ll val = abs(a.ft - b.ft);
        p.emplace_back(u, v, val);
    };
    for (int i = 1; i < n; i++) {
        foo(p1[i], p1[i - 1]);
        foo(p2[i], p2[i - 1]);
        foo(p3[i], p3[i - 1]);
    }
    sort(all(p), [&](const auto &a, const auto &b) {
        return a.c < b.c;
    });

    ll ans = 0;
    for (const Edge &e: p) {
        auto[u, v, c] = e;
        u = find(u);
        v = find(v);
        if (u != v) {
            par[u] = v;
            ans += c;
        }
    }
    cout << ans;
}