[c++][백준 2887] 행성 터널

백준 2887번: 행성 터널 [Gold 1]
https://www.acmicpc.net/problem/2887

2887번: 행성 터널

문제 풀이

• 이 문제는 MST(Minimum Spanning Tree)를 구하는 문제입니다. 
• 처음 문제를 읽으면서 MST를 구해야 하는 것을 파악한 후 Edge의 개수가 매우 많을 것 같아 Kruskal과 Prim 중 Prim을 사용했습니다. 하지만 최대 노드 개수가 100000이기 때문에 Edge 개수는 최대 100000 * 99999가 되고 테스트 과정에서 메모리 초과가 발생했습니다.
• 풀이 방법이 생각나지 않아서 다른 분들의 풀이를 찾아본 결과 x, y, z별로 노드들을 정렬한 후 (i, i+1)을 짝 지은 Edge만 사용, 즉 비용이 최소가 될 수 있는 Edge들을 3(N-1) 개를 추려내어 Kruskal로 구현했습니다. 

코드

#include <cstdio>
#include <algorithm>
#include <tuple>
#include <cstring>

using namespace std;

int N;

vector<pair<int,int>> node[3];
vector<tuple<int,int,int>> edge; 
int parent[100010];

int find(int n) {
    if(parent[n] < 0) return n;
    return parent[n] = find(parent[n]); 
}

int main() {
    memset(parent, -1, sizeof(parent));

    scanf("%d", &N);

    for(int i=0; i<N; ++i) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);

        node[0].push_back({x, i});
        node[1].push_back({y, i});
        node[2].push_back({z, i});
    }

    sort(node[0].begin(), node[0].end());
    sort(node[1].begin(), node[1].end());
    sort(node[2].begin(), node[2].end());

    for(int i=0; i<N-1; ++i) {
        edge.push_back({node[0][i+1].first - node[0][i].first, node[0][i].second, node[0][i+1].second});
        edge.push_back({node[1][i+1].first - node[1][i].first, node[1][i].second, node[1][i+1].second});
        edge.push_back({node[2][i+1].first - node[2][i].first, node[2][i].second, node[2][i+1].second});
    }

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

    int cnt = 0, answer = 0;
    for(auto e: edge) {
        auto [cost, from, to] = e;

        from = find(from);
        to = find(to);
        if(from != to) {
            cnt++;
            answer += cost;
            parent[from] = to;

            if(cnt == N-1) break;
        }
    }

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

    return 0;
}

실행 결과