2887번 행성 터널

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

나는 x → y → z를 한 번에 정렬하여 순서대로 min 값을 찾는 방법을 생각하였으나

1  1000  3

1000 1000 

위와 같은 좌표들이 있을 수도 있어서 반례가 생기고,

메모리 초과가 발생하였다.(N = 100,000)

알고 보니, 각각을 정렬하여 활용하는 방법이 있었다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 100001
 
struct info { int x, y, z, num; };
struct info2 { int a, b, c; };
 
int N, parent[Max];
vector<info> v;
vector<info2> mst;
 
bool cmpx(const info & a, const info & b) { return a.x < b.x; }
bool cmpy(const info & a, const info & b) { return a.y < b.y; }
bool cmpz(const info & a, const info & b) { return a.z < b.z; }
bool cmp(const info2 & a, const info2 & b) { return a.c < b.c; }
 
int Find(int x)
{
    if (parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}
 
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
int main(void)
{
    //cin.tie(0);
 
    int x, y, z, cnt = 0, answer = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        parent[i] = i;
        scanf("%d %d %d", &x, &y, &z);
        v.push_back({ x, y, z, i });
    }
 
    // x
    sort(v.begin(), v.end(), cmpx);
    for (int i = 0; i < v.size() - 1; i++) mst.push_back({ v[i].num, v[i + 1].num, abs(v[i].x - v[i + 1].x) });
 
    // y
    sort(v.begin(), v.end(), cmpy);
    for (int i = 0; i < v.size() - 1; i++) mst.push_back({ v[i].num, v[i + 1].num, abs(v[i].y - v[i + 1].y) });
 
    // z
    sort(v.begin(), v.end(), cmpz);
    for (int i = 0; i < v.size() - 1; i++) mst.push_back({ v[i].num, v[i + 1].num, abs(v[i].z - v[i + 1].z) });
 
    sort(mst.begin(), mst.end(), cmp);
 
    for (auto i : mst)
        if (Find(i.a) != Find(i.b))
        {
            Union(i.a, i.b);
            answer += i.c;
            if (++cnt == N - 1) break;
        }
 
    printf("%d\n", answer);
 
    return 0;
}