BOJ 2887 : 행성 터널

3줄요약

• 아이디어
• 최소 스패닝 트리
• 정렬

 

서론

 

이 문제는 최소 스패닝 트리에 아이디어를 결합한 문제이다. 골드 1치고는 매우 어렵다고 생각한다.

 

 

본론

 

N <= 100,000 이니, 거리를 모두 계산해 간선을 추가하여 MST를 돌리는 방법은 O(N^2)로 시간초과가 나서 안된다. 이때 우리는 창의적으로 생각할 수 있어야 한다; 간선을 추가하되, 모든 간선을 추가하지 않는 방법이 존재하는가?

있다. 일단 문제 자체를 보자. 왜 최소 길이를 min(|xA-xB|, |yA-yB|, |zA-zB|) 로 구하는지 알아야 한다.

이의 뜻을 풀어보면, 행성 A와 행성 B의 |xA-xB|, |yA-yB|, |zA-zB| 중 최솟값의 최솟값 이므로, 우리의 목표는 행성 A와 가장 |xA-xB|, |yA-yB|, |zA-zB| 가 작은 행성을 찾아 두 행성을 잇는 것이다. 그러면 그것을 어떻게 구할까? 바로 정렬이다.

 

한번 문제의 예제를 좌표값이 작은 순서대로 정렬해보자.

 

X	-1 (3)	10 (4)	11 (1)	14 (2)	19 (5)
Y	-15 (1)	-5 (2)	-1 (3)	-4 (4)	-4 (5)
Z	-15 (1)	-15 (2)	-5 (3)	-1 (4)	19 (5)

 

여기서 규칙을 찾을 수 있다. i번째 인덱스 에서 가장 가까운 행성은 i-1번째 인덱스 혹은 i+1번째 인덱스라는 것이다.

한번 X의 10 테이블을 보자. 가장 가까운 X는 10 옆의 11, 바로 오른쪽에 있는 인덱스이다. 다른 것도 마찬가지이다.

그럼, 4와 1을 잇는 최솟값은 뭘까? 우리가 구한 X에서의 값 1, Y에서의 값 11, Z에서의 값 14 중 최솟값은 1,

1과 4를 잇는 최솟값은 1이 된다. 우리는 모든 간선을 추가하는 대신, 정렬하여 바로 옆의 것만 넣으면 된다는 결론에 도달했다. 그래서, 간선은 N^2개에서 6N(확인하는건 3N)개로 바뀌어, 시간 복잡도 내에 해결을 할 수 있게 된다. 이제 MST와 응용해보자. 사실 이건 별로 어렵지 않다. 우리가 구한 X에서의 값, Y에서의 값, Z에서의 값을 모두 간선 배열에 넣어 정렬하면 된다. 이후엔 그 간선 배열로 MST를 돌리면 된다. 코드는 밑에 있다.

 

 

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
#define MAXN 100001
#define INF 2147483647

int N;
int parent[MAXN];
vector<pair<int, int> > loc[3];
vector<pair<int, pair<int, int> > > E;

int Find(int node) {
    if (parent[node] == node) return node;
    else return parent[node] = Find(parent[node]);
}

void Union(int node1, int node2) {
    node1 = Find(node1); node2 = Find(node2);
    if (node1 != node2) parent[node2] = node1;
}

int main() {

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int x, y, z; scanf("%d %d %d", &x, &y, &z);
        loc[0].push_back({ x, i }); loc[1].push_back({y, i}); loc[2].push_back({z, i});
    }

    for (int i = 0; i < 3; i++) {
        sort(loc[i].begin(), loc[i].end());
    }
    
    for (int j = 0; j < 3; j++) {
        for (int i = 1; i < N; i++) {
            int dist = abs(loc[j][i].first - loc[j][i - 1].first);
            int from = loc[j][i].second; int to = loc[j][i - 1].second;
            E.push_back({dist, {from, to}});
        }
    }

    sort(E.begin(), E.end());
    for (int i = 0; i < N; i++) parent[i] = i;

    int ans = 0;
    for (int i = 0; i < E.size(); i++) {
        
        int from = E[i].second.first;
        int to = E[i].second.second;
        int dist = E[i].first;

        int x = Find(from); int y = Find(to);
        if (x == y) { continue; }

        Union(from, to); ans += dist;
    }

    printf("%d", ans);
}

 

결론

 

이 문제는 어렵다.

 

난이도(개인적): Platinum IV
난이도(객관적): Gold I

 

Contact: How2Contact (tistory.com)