[Baekjoon/C++] 2887번 - 행성 터널

[백준] Baekjoon Online Judge

문제로 이동

 

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

---

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    int start = 0;
    int end = 0;
    long long weight = 0;
};

int N, parent[100001];
vector<pair<int, int>> x, y, z;
vector<Edge> edge;

bool compare(Edge a, Edge b);
int findParent(int n);
long long mst();

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int findParent(int n) {
    if (parent[n] == 0 || parent[n] == n) return n;

    return parent[n] = findParent(parent[n]);
}

long long mst() {
    long long result = 0;

    for (int i = 0; i < edge.size(); i++) {
        int a = findParent(edge[i].start);
        int b = findParent(edge[i].end);

        if (a != b) {
            parent[b] = a;
            result += edge[i].weight;
        }
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i < N + 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        x.push_back({ a, i });
        y.push_back({ b, i });
        z.push_back({ c, i });
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    sort(z.begin(), z.end());

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

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

    cout << mst() << '\n';

    return 0;
}

 최소 스패닝 트리를 구현하여 문제를 풀었다.

 

    cin >> N;
    for (int i = 1; i < N + 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        x.push_back({ a, i });
        y.push_back({ b, i });
        z.push_back({ c, i });
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    sort(z.begin(), z.end());

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

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

 main함수의 코드이다. 행성 좌표의  x, y, z 값을 각각 다른 벡터에 저장한 뒤 이를 정렬한다. 그 뒤 좌표끼리 인접한 행성들의 연결만을 edge에 저장하도록 했다. 서로 인접하지 않은 행성들의 연결은 그렇지 않은 연결보다 효율적이지 않기에 최소 스패닝 트리에서 선택되지 않을 것이며, 이런 연결을 모두 edge에 저장하면 메모리 초과가 발생할 수 있기 때문이다.

 

int findParent(int n) {
    if (parent[n] == 0 || parent[n] == n) return n;

    return parent[n] = findParent(parent[n]);
}

long long mst() {
    long long result = 0;

    for (int i = 0; i < edge.size(); i++) {
        int a = findParent(edge[i].start);
        int b = findParent(edge[i].end);

        if (a != b) {
            parent[b] = a;
            result += edge[i].weight;
        }
    }

    return result;
}

 최소 스패닝 트리를 만드는 함수이다.