[2887번] 행성 터널

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 유니온 파인드(Union Find) :: http://www.crocus.co.kr/683

2. 최소 스패닝 트리(MST) :: http://www.crocus.co.kr/733

이 문제는 문제 내용에서 힌트를 얻어야 해결 할 수 있다.

현재 각 정점간의 최단 거리를 min(|xA-xB|, |yA-yB|, |zA-zB|)로 정의하고있다.

즉, 최소 스패닝 트리로 접근 하기위해 x,y,z로 이루어진 idx들을 이용하여 정점들을 연결해주면 된다.

이때 min방식을 어떻게 이용할 것이냐면

x에 대해 정렬을 해주면 idx가 이리저리 섞일 것이고

그 인접한 x끼리 거리를 구해 거리와 idx를 pq에 넣어준다.

y도 y에 대해 정렬을 해주면 idx가 이리저리 섞일 것이고

그 인접한 y끼리 거리를 구해 거리와 idx를 pq에 넣어준다.

마지막으로 z에 대해 정렬을 해주면 idx가 이리저리 섞일 것이고

그 인접한 z끼리 거리를 구해 거리와 idx를 pq에 넣어준다.

이렇게되면 pq에는 가장 짧은 거리부터 idx들이 나타날 것이다.

결국 이 방식으로 행성을 연결해주면 최소 스패닝 트리를 이루는 행성을 만들 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cmath>   using namespace std;   typedef pair<int, int> pii;   typedef struct _INFO_ {     int x;     int y;     int z;     int idx; }INFO;   INFO info[100001]; int parent[100001]; long long ans; bool chk;   bool compx(const INFO &a, const INFO &b) {     return a.x < b.x; } bool compy(const INFO &a, const INFO &b) {     return a.y < b.y; } bool compz(const INFO &a, const INFO &b) {     return a.z < b.z; }   int find(int u) {     if (u == parent[u])         return u;       return parent[u] = find(parent[u]); }   void merge(int u, int v) {     chk = false;     u = find(u);     v = find(v);       if (u == v)         return;       parent[u] = v;     chk = true; }   int main() {     int n;       scanf("%d", &n);       for (int i = 0; i < n; i++)         parent[i] = i;       // 정보 입력     for (int i = 0; i < n; i++)     {         scanf("%d %d %d", &info[i].x, &info[i].y, &info[i].z);         info[i].idx = i;     }       priority_queue<pair<int, pair<int, int>>> pq;       // x에 대해 정렬하여 인접한 x끼리 길이를 구해 pq에 push한다.     sort(info, info + n, compx);     for (int i = 1; i < n; i++)         pq.push({ -abs(info[i].x - info[i - 1].x), pii(info[i].idx, info[i - 1].idx) });       // y에 대해 정렬하여 인접한 y끼리 길이를 구해 pq에 push한다.     sort(info, info + n, compy);     for (int i = 1; i < n; i++)         pq.push({ -abs(info[i].y - info[i - 1].y), pii(info[i].idx, info[i - 1].idx) });       // z에 대해 정렬하여 인접한 z끼리 길이를 구해 pq에 push한다.     sort(info, info + n, compz);     for (int i = 1; i < n; i++)         pq.push({ -abs(info[i].z - info[i - 1].z), pii(info[i].idx, info[i - 1].idx) });       // 위에서 구한 과정으로 작은 값 순서로 idx를 서로 merge해준다.     while (!pq.empty())     {         int val = -pq.top().first;         int idx1 = pq.top().second.first;         int idx2 = pq.top().second.second;           pq.pop();         merge(idx1, idx2);           // merge가 성공하면         if (chk)             ans += val;     }       printf("%lld", ans);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus