BOJ - 행성 터널(2887)

처음에 이 문제를 접했을 때, 사실 왜 gold 1이나 부여되어 있는지 몰랐는데 그대로 제출하니 메모리 초과가 발생하였다. 

 

N이 10만개가 들어왔을 경우 내 알고리즘은 현재 N * (N-1)개 만큼의 간선정보를 저장하고 있다. 하지만, 이 문제는 모든 간선에 대한 정보를 알 필요 없이 x축, y축, z축에 대해 인접한 행성만 보면 된다. 그 이유는 백준 질문게시판에 나와있는 아래 내용과 같다.

주어진 그래프의 MST를 T라고 합시다.  인접하지 않은 정점 A, B가 T에서 간선으로 연결되어있다고 가정하죠. 일반성을 잃지 않고 A, B 사이에 연결된 간선 무게가 |A_x - B_x| 라고 하죠. x 축으로 A, B 사이에 있는 정점 C가 존재합니다 (A_x <= C_x <= B_x) 여기서 A, B를 연결하는 간선을 제거하고 A, C 와 C, B를 연결합니다 (이 그래프를 G라고 하죠) G는 N개의 간선으로 이루어져 있고, 연결되어있다는건 자명합니다. 그리고 총 무게 변화는 최대 -|A_x - B_x| + |A_x - C_x| + |C_x - B_x| = 0 입니다. 즉 G의 싸이클에서 간선 아무거나 지워도 T보다 총 무게가 더 작습니다. T가 MST라는 가정이 모순되니 MST에서 연결된 정점은 인접합니다.

코드 

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
typedef long long ll;
typedef struct coor
{
    ll x,y,z;
    int idx;
}coor;
 
typedef struct graph
{
    int v1, v2;
    ll cost;
}graph;
 
vector<coor> v;
vector<graph> g;
 
int getRoot(vector<int> &parent, int idx)
{
    if (parent[idx] == idx) return idx;
    else return parent[idx] = getRoot(parent, parent[idx]);
}
 
void merge(vector<int> &parent, int a, int b)
{
    a = getRoot(parent, a); b = getRoot(parent, b);
    if (a == b) return;
    else if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
bool comp(graph a, graph b)
{
    return a.cost < b.cost;
}
 
bool compX(coor a, coor b)
{
    return a.x < b.x;
}
 
bool compY(coor a, coor b)
{
    return a.y < b.y;
}
 
bool compZ(coor a, coor b)
{
    return a.z < b.z;
}
 
int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> N;
    for(int i=0; i<N; i++)
    {
        coor c;
        cin >> c.x >> c.y >> c.z;
        c.idx = i + 1;
        v.push_back(c);
    }
    sort(v.begin(), v.end(), compX);
    for(int i=1; i<N; i++)
    {
        long long dist = min(min(abs(v[i-1].x - v[i].x), abs(v[i-1].y - v[i].y)), abs(v[i-1].z - v[i].z));
        graph tmp;
        tmp.v1 = v[i-1].idx;
        tmp.v2 = v[i].idx;
        tmp.cost = dist;
        g.push_back(tmp);
    }
    sort(v.begin(), v.end(), compY);
    for(int i=1; i<N; i++)
    {
        long long dist = min(min(abs(v[i-1].x - v[i].x), abs(v[i-1].y - v[i].y)), abs(v[i-1].z - v[i].z));
        graph tmp;
        tmp.v1 = v[i-1].idx;
        tmp.v2 = v[i].idx;
        tmp.cost = dist;
        g.push_back(tmp);
    }
    sort(v.begin(), v.end(), compZ);
    for(int i=1; i<N; i++)
    {
        long long dist = min(min(abs(v[i-1].x - v[i].x), abs(v[i-1].y - v[i].y)), abs(v[i-1].z - v[i].z));
        graph tmp;
        tmp.v1 = v[i-1].idx;
        tmp.v2 = v[i].idx;
        tmp.cost = dist;
        g.push_back(tmp);
    }
    sort(g.begin(), g.end(), comp);
    long long sum = 0;
    vector<int> parent(N + 1);
    for(int i=1; i<=N; i++)
        parent[i] = i;
    for(int i=0; i<g.size(); i++)
    {
        int v1 = g[i].v1; int v2 = g[i].v2;
        if (getRoot(parent, v1) != getRoot(parent, v2))
        {
            merge(parent, v1, v2);
            sum += g[i].cost;
        }
    }
    cout << sum << "\n";
    return (0);
}

위 코드와 같이 X, Y, Z축에 대해 각각 정렬한 뒤 인접한 행성들의 간선들을 모두 g에 저장한다. 그러면 6 * N개 만큼의 정보가 저장되어 있으므로 간선의 개수가 확연히 줄은 것을 알 수 있다. 

이에 대해 크루스칼 알고리즘을 적용하면 쉽게 답을 구할 수 있다.