BOJ 2887 행성 터널

📝 문제 정보

링크: https://www.acmicpc.net/problem/2887

🧐 관찰 및 접근

누가봐도 MST를 짜야하는거같은데..
행성 두개에 대해 모두 생각하면 간선의 개수가 $N^2$개가 된다…
그런데, 생각해보면 만약 행성 $A, B, C$가 있고, 세개 모두 $x$를 기준으로 연결했다고 하자.
- $x_A < x_B < x_C$라면, $x_A$와 $x_C$의 관계를 신경 쓸 필요가 있을까?
  - 없다!!
- 따라서, $x, y, z$ 각각에 대해 정렬한 간선 $3N$개정도를 이용해서 MST를 짜자.

💻 풀이

코드 (C++):

void solve(){
    int N; cin >> N;
    vector<array<ll, 4>> planets;
    rep(i, 0, N){
        int x, y, z; cin >> x >> y >> z;
        planets.push_back({x, y, z, i});
    }
    vector<array<ll, 3>> edges;
    sort(all(planets), [](auto &a, auto &b){
        return a[0] < b[0];
    });
    rep(i, 0, N-1) edges.push_back({abs(planets[i][0]-planets[i+1][0]), planets[i][3], planets[i+1][3]});
    sort(all(planets), [](auto &a, auto &b){
        return a[1] < b[1];
    });
    rep(i, 0, N-1) edges.push_back({abs(planets[i][1]-planets[i+1][1]), planets[i][3], planets[i+1][3]});
    sort(all(planets), [](auto &a, auto &b){
        return a[2] < b[2];
    });
    rep(i, 0, N-1) edges.push_back({abs(planets[i][2]-planets[i+1][2]), planets[i][3], planets[i+1][3]});
    sort(all(edges));
    UF.init(N);
    ll ans = 0;
    for(auto [w, u, v]: edges) if(UF.merge(u, v)) ans += w;
    cout << ans << '\n';
}