알고리즘 :: 백준 :: 그래프 :: 2887 :: 행성 터널

문제

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

행성은 3차원 좌표 위의 한 점으로 주어지며 두 행성을 연결하는 터널의 비용은 $min(|x_A-x_B|, |y_A-y_B|, |z_A-z_B|)$이다. 터널을 $N-1$개 건설해서 모든 행성이 서로 연결되게 하려 할 때 필요한 최소 비용을 구하라. (1 ≤ N ≤ 100,000)

문제접근

• MST 문제이지만 조금 복잡한 원인이 두 가지 있다.
  1. 간선이 입력으로 주어지는 기존의 문제들과는 달리 정점의 좌표가 주어지므로 직접 간선의 cost를 계산해야 한다.
  2. N이 최대 10만까지이므로 크루스칼 알고리즘을 위해 모든 간선을 저장한다면, 총 100억 바이트의 공간이 필요해서 메모리 초과가 난다.
• 따라서 이 문제를 슬기롭게 해결하기 위해서는 모든 간선을 계산하지 않으면서 해결할 수 있어야 한다.

1. 정점의 3차원 좌표들을 입력받아 배열에 저장한다.
2. 입력된 N개의 정점들을 x좌표에 대해 정렬하고 이를 cost배열에 저장한다.
3. 입력된 N개의 정점들을 x좌표에 대해 정렬하고 이를 cost배열에 저장한다.
4. 입력된 N개의 정점들을 x좌표에 대해 정렬하고 이를 cost배열에 저장한다.
5. cost 배열을 오름차순으로 정렬한다.
6. 이제 cost 배열의 앞에서부터 사이클이 발생 여부를 확인하면서 크루스칼 알고리즘을 수행해서 MST를 생성한다.

• 이 방법을 사용하면 10만 X 10만 만큼의 배열에 간선을 저장할 필요가 없다.

코드

// https://www.acmicpc.net/problem/2887
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct Point { int x, y, z, idx; } Point;
typedef struct Info { int sv, ev, cost; } Info;
static int rootInfo[100001];
static vector<Point> vertex;
static vector<Info> mst;

int findOperation(int x) {
    if (rootInfo[x] != x) return findOperation(rootInfo[x]);
    return rootInfo[x];
}
void unionOperation(int lhs, int rhs) {
    lhs = findOperation(lhs), rhs = findOperation(rhs);
    (lhs < rhs) ? (rootInfo[rhs] = lhs) : (rootInfo[lhs] = rhs);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int N;  cin >> N;
    for (int i = 1; i <= N; ++i) {
        int x, y, z;    cin >> x >> y >> z;
        vertex.push_back({x, y, z, i});
        rootInfo[i] = i;
    }
    // n = 최대 100,000이므로 O(n^2) 시간,공간 복잡도로 풀 수 없다!
    // x에 대해서 정렬하고, cost 차이를 mst 배열에 넣는다.
    sort(begin(vertex), end(vertex), [](const Point& lhs, const Point& rhs){ return lhs.x < rhs.x; });
    for (int i = 0; i < N - 1; ++i)
        mst.push_back({vertex[i].idx, vertex[i + 1].idx, abs(vertex[i].x - vertex[i + 1].x)});
    // y에 대해서 정렬하고, cost 차이를 mst 배열에 넣는다.
	sort(begin(vertex), end(vertex), [](const Point& lhs, const Point& rhs){ return lhs.y < rhs.y; });
    for (int i = 0; i < N - 1; ++i)
        mst.push_back({vertex[i].idx, vertex[i + 1].idx, abs(vertex[i].y - vertex[i + 1].y)});
    // z에 대해서 정렬하고, cost 차이를 mst 배열에 넣는다.
	sort(begin(vertex), end(vertex), [](const Point& lhs, const Point& rhs){ return lhs.z < rhs.z; });
    for (int i = 0; i < N - 1; ++i)
        mst.push_back({vertex[i].idx, vertex[i + 1].idx, abs(vertex[i].z - vertex[i + 1].z)});
    // mst 배열을 cost 순으로 오름차순 정렬한다.
	sort(begin(mst), end(mst), [](const Info& lhs, const Info& rhs){ return lhs.cost < rhs.cost; });
	
    // 크루스칼 알고리즘을 수행한다.
    int answer = 0, edgeCnt = 0;
    for (const auto& itr : mst)
        if (findOperation(itr.sv) != findOperation(itr.ev)) {
            unionOperation(itr.sv, itr.ev);
            answer += itr.cost;
            if (++edgeCnt == N - 1) break;  // MST의 간선 개수는 N - 1개다.
        }
    cout << answer << '\n';
}

결과