2887번 행성 터널

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

 

지난 풀이 : https://hsdevelopment.tistory.com/417

 

일반적인 MST로는 메모리 초과가 발생한다.

 

처음에는 모든 행성들 간에 각각 행성의 x, y, z 및 이중 for문을 활용해, vector에 담는 방법을 생각할 수 있지만.

최대 10만개라서, 메모리 초과가 발생한다.

 

생각해볼 수 있는건 

 

행성 A : xa, ya, za

행성 B : xb, yb, zb

 

일 때의 거리로 인정 받는 최솟값은 min(|xa-xb|, |ya-yb|, |za-zb|)라는 점이다.

 

즉, 행성 A와 행성 B를 이중 for문을 통해 담는 것이 아니라,

 

x 좌표, y 좌표, z 좌표끼리 각각 vector에 담아서 구현할 수 있다.

 

1. x좌표를 vector에 담는다. → 오름차순 정렬

예시) 3(a), 4(b), 2(c) 일 경우, 오름차순 정렬하면, 2(c), 3(a), 4(b)가 된다.

이 때, 행성 c와 행성 a의 최소 x 거리는 1이다. 

행성 c와 행성 b의 최소 x 거리는 1이다.

최소 x 거리 보장

 

2. y좌표를 vector에 담는다. → 오름차순 정렬

최소 y 거리 보장

 

3. z좌표를 vector에 담는다. → 오름차순 정렬

최소 z 거리 보장

 

위 1, 2, 3을 모두 하나의 vector<tuple<int, int, int> > 담은 후에 거리 순으로 오름차순 정렬한다.

 

#include <bits/stdc++.h>

using namespace std;

int N;
int p[100001];
vector<pair<int, int> > vx, vy, vz;
vector<tuple<int, int, int> > vt;

int Find(int x) {
    if (x == p[x]) return x;
    return p[x] = Find(p[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a < b) p[b] = a;
    else p[a] = b;
}

int main()
{
    int x, y, z;

    scanf("%d", &N);

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

    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &x, &y, &z);
        vx.push_back({ x, i });
        vy.push_back({ y, i });
        vz.push_back({ z, i });
    }

    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    sort(vz.begin(), vz.end());

    int idx = 0;
    for (int i = 0; i < N - 1; i++) {
        // x
        int distStart = vx[i].first;
        int start = vx[i].second;
        int distEnd = vx[i + 1].first;
        int end = vx[i + 1].second;
        vt.push_back({ abs(distStart - distEnd), start, end });

        // y
        distStart = vy[i].first;
        start = vy[i].second;
        distEnd = vy[i + 1].first;
        end = vy[i + 1].second;
        vt.push_back({ abs(distStart - distEnd), start, end });

        // z
        distStart = vz[i].first;
        start = vz[i].second;
        distEnd = vz[i + 1].first;
        end = vz[i + 1].second;
        vt.push_back({ abs(distStart - distEnd), start, end });
    }

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

    int cnt = 0, sum = 0;

    for (auto i : vt) {
        int dist = 0, st = 0, ed = 0;
        tie(dist, st, ed) = i;
        if (Find(st) != Find(ed)) {
            Union(st, ed);
            sum += dist;
            if (++cnt == N - 1) {
                break;
            }
        }
    }

    printf("%d\n", sum);

    return 0;
}