백준 2887번 [행성 터널](C++) -yes6686- 티스토리

백준 문제 풀이: 2887 [행성 터널]

---

문제 링크: https://www.acmicpc.net/problem/2887

문제 설명:

N개의 행성이 3차원 좌표에 위치하고 있으며, 특정 행성들 사이를 터널로 연결하려고 합니다. 터널의 비용은 두 행성 간의 거리로 정의됩니다. 모든 행성을 연결하면서 최소 비용으로 터널을 구성하려면 어떻게 해야 할까요?

---

문제 해결 코드

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

int parent[100001];

struct st {
    int x, y, z;
    int num;
};

struct edge {
    int a, b;
    int dis;
};

edge Ed[300001];
st St[100001];

int GetParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = GetParent(parent[x]);
}

void unionParent(int a, int b) {
    a = GetParent(a);
    b = GetParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}

int findParent(int a, int b) {
    a = GetParent(a);
    b = GetParent(b);
    return a == b;
}

bool compare(edge a, edge b) {
    return a.dis < b.dis;
}

bool compareX(st a, st b) { return a.x < b.x; }
bool compareY(st a, st b) { return a.y < b.y; }
bool compareZ(st a, st b) { return a.z < b.z; }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> St[i].x >> St[i].y >> St[i].z;
        St[i].num = i;
    }
    for (int i = 0; i < n; i++) parent[i] = i;

    int kk = 0;
    sort(St, St + n, compareX);
    for (int i = 1; i < n; i++) {
        Ed[kk++] = {St[i - 1].num, St[i].num, abs(St[i].x - St[i - 1].x)};
    }
    sort(St, St + n, compareY);
    for (int i = 1; i < n; i++) {
        Ed[kk++] = {St[i - 1].num, St[i].num, abs(St[i].y - St[i - 1].y)};
    }
    sort(St, St + n, compareZ);
    for (int i = 1; i < n; i++) {
        Ed[kk++] = {St[i - 1].num, St[i].num, abs(St[i].z - St[i - 1].z)};
    }

    sort(Ed, Ed + kk, compare);
    long long sum = 0;
    for (int i = 0; i < kk; i++) {
        if (!findParent(Ed[i].a, Ed[i].b)) {
            unionParent(Ed[i].a, Ed[i].b);
            sum += Ed[i].dis;
        }
    }
    cout << sum << '\n';
}

예제

입력:
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

출력:
4

---

코드 설명

• 입력 처리:
  • 각 행성의 좌표와 번호를 저장합니다.
• 터널 비용 계산:
  • x, y, z 좌표를 각각 기준으로 정렬한 뒤, 인접한 행성 간의 거리 정보를 저장합니다.
• 크루스칼 알고리즘:
  • 최소 스패닝 트리를 구하기 위해 크루스칼 알고리즘을 사용합니다.
  • 거리가 짧은 간선부터 연결하며, 사이클이 발생하지 않도록 부모 노드 정보를 업데이트합니다.

시간 복잡도

• 정렬: O(n log n)
• 크루스칼 알고리즘: O(E log E)
• 총 시간 복잡도: O(n log n + E log E), 여기서 E는 간선의 개수입니다.

---

결과

위 코드는 입력된 좌표를 바탕으로 최소 비용으로 모든 행성을 연결하는 터널을 계산합니다.