[백준 BoJ] 2887 - 행성터널

// 메모리 초과 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<cmath>
using namespace std;
int N;
int parent[100002];

vector<tuple<int, int, int>> star;
vector<tuple<int, int, long long>> nebula;
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;
}
void kruscal() {
    long long sum = 0;
    for (auto n : nebula) {
        int a = get<0>(n);
        int b = get<1>(n);
        long long cost = get<2>(n);
        if (Find(a) != Find(b)) {
            sum += cost;
            Union(a, b);
        }
    }
    cout << sum;
}
void difference(int a, int b) {
    long long x = abs(get<0>(star[a]) - get<0>(star[b]));
    long long y = abs(get<1>(star[a]) - get<1>(star[b]));
    long long z = abs(get<2>(star[a]) - get<2>(star[b]));

    nebula.push_back(make_tuple(a, b, min({ x, y, z })));
}
bool cmp(tuple<int, int, long long> a, tuple<int, int, long long> b) {
    return get<2>(a) < get<2>(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) parent[i] = i;

    for (int i = 0; i < N; i++) {
        int x, y, z;

        cin >> x >> y >> z;
        star.push_back(make_tuple(x, y, z));
    }

    for (int i = 0; i < star.size(); i++) {
        for (int j = i + 1; j < star.size(); j++) {
            difference(i, j);
        }
    }

    sort(nebula.begin(), nebula.end(), cmp);
    star.clear();
    kruscal();
}

 

행성의 최대 크기가 100,000이기 때문에 간선은 100,000 * 100,000가 발생할 수 있다. vector를 int형 튜플로 작성했을 때 12byte가 10,000,000,000개 생성되므로 약 111GB가 생성될 수 있다. 그래서 각 x, y, z축별로 오름차순 정렬한 뒤 크루스칼 알고리즘을 이용해 구하면 해결 할 수 있다.

만약 x축별로 연결했지만 어떤 y하나가 더 가까우면 어떡하지라는 생각을 했었지만 parent 배열에 최신화를 하기 때문에 상관 없었다.

 

// https://www.acmicpc.net/problem/2887
// 행성 터널

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<cmath>
using namespace std;
int N;
int parent[100002];

vector<pair<int, int>> X;
vector<pair<int, int>> Y;
vector<pair<int, int>> Z;
vector<tuple<int, int, long long>> nebula;
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;
}
void kruscal() {
    long long sum = 0;
    for (auto n : nebula) {
        int a = get<0>(n);
        int b = get<1>(n);
        long long cost = get<2>(n);
        if (Find(a) != Find(b)) {
            sum += cost;
            Union(a, b);
        }
    }
    cout << sum;
}
bool cmp(tuple<int, int, long long> a, tuple<int, int, long long> b) {
    return get<2>(a) < get<2>(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) parent[i] = i;

    for (int i = 0; i < N; i++) {
        int x, y, z;

        cin >> x >> y >> z;
        X.push_back(make_pair(x, i));
        Y.push_back(make_pair(y, i));
        Z.push_back(make_pair(z, i));
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    sort(Z.begin(), Z.end());

    for (int i = 0; i < N - 1; i++) {
        nebula.push_back(make_tuple(X[i].second, X[i + 1].second, abs(X[i + 1].first - X[i].first)));
        nebula.push_back(make_tuple(Y[i].second, Y[i + 1].second, abs(Y[i + 1].first - Y[i].first)));
        nebula.push_back(make_tuple(Z[i].second, Z[i + 1].second, abs(Z[i + 1].first - Z[i].first)));
    }

    sort(nebula.begin(), nebula.end(), cmp);

    kruscal();
}