[C/C++] 백준 #2887 행성 터널(크루스칼 알고리즘)

이번 문제는 크루스칼 알고리즘을 이용해서 풀었습니다.

 

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

 

하지만, V개의 행성을 모두 연결한다면, $V(V-1)$만큼의 간선이 생기므로, 정렬을 할 때, 주어진 V값에 대해서 느려질 수 있습니다.

간선의 갯수는 최소 비용 신장 트리(Minimum Spanning Tree)를 프림 알고리즘을 이용하든, 크루스칼 알고리즘을 이용하든 모두 시간 복잡도가 주어진 V값의 최대치라면, 시간초과가 됩니다.  $E=V(V-1)$이 된다면, 프림 알고리즘 상에서는 $O(E\log V)=O(V^2\log V)$, 크루스칼 알고리즘 상에서는 $O(E\log E)=O(V^2\log V$ 형태가 되겠죠.  물론 프림 알고리즘을 구현할 때 피보나치 힙을 구성하면 더 빠르게 할 수 있습니다.

 

planet tunnel

 

그래서 가장 중요한 알고리즘은 거리를 계산하는 공식의 특성에서 찾아서 했습니다.  각 축 중 가장 적은 값을 이용하므로, 각 축별로 행성을 정렬한 후에 이웃하는 것끼리 간선을 만듭니다.  겹치는 간선이 있을 수 있지만 그것은 무시합니다.

 

문제 분석 및 해결 방법

문제의 본질은 3차원 공간에 있는 n개의 행성을 최소 비용으로 연결하는 것입니다. 이를 해결하기 위해 다음과 같은 접근 방식을 사용합니다.

1. **행성 간 거리 계산**:
   행성 간의 거리는 터널을 구축하는 데 드는 비용으로 간주되며, 이 거리는 행성 간 좌표 차이의 절대값 중 가장 작은 값으로 정의됩니다. 예를 들어, 두 행성 $A(x1,y1,z1)$와 $B(x2,y2,z2)$ 사이의 거리는 다음과 같이 계산됩니다:
   $$\text{DISTANCE}(A,B)=min(|x1-x2|,|y1-y2|,|z1-z2|)$$

2. **간선 생성**:
   행성들을 연결하기 위한 간선(Edge)은 행성 간의 거리로 정의되며, 이를 기준으로 간선 목록을 생성합니다. 주어진 좌표를 기준으로 각 축(x, y, z)별로 정렬하여 인접한 행성들 간의 거리로 간선을 생성합니다. 이렇게 하면 $n-1$개의 간선이 각 축에 대해 만들어지므로 총 3(n-1)개의 간선이 생성됩니다.

3. **최소 스패닝 트리 구성**:
   크루스칼 알고리즘(Kruskal's Algorithm)을 사용하여 최소 스패닝 트리를 구성합니다. 크루스칼 알고리즘은 간선을 가중치 오름차순으로 정렬한 후, 가장 낮은 가중치의 간선부터 차례로 선택하면서 사이클이 생기지 않도록 간선을 추가하는 방식으로 동작합니다.
   
   이 과정에서 서로소 집합(Union-Find) 자료구조를 이용해 간선이 사이클을 형성하는지 여부를 확인합니다. 각 행성은 처음에 자기 자신을 부모로 가지며, 연결된 행성들의 집합은 같은 부모를 공유하게 됩니다.

코드 상세 설명

1. **구조체 정의**:

   struct Coord { int p, x, y, z; } c[100000];
   struct Edge { int a, b, c; } e[300000];

   - `Coord` 구조체는 행성의 좌표와 행성의 번호를 저장합니다.
   - `Edge` 구조체는 두 행성 사이의 간선을 나타내며, `a`와 `b`는 연결된 두 행성의 번호, `c`는 이들 간의 거리(즉, 비용)를 저장합니다.

2. **정렬 함수 정의**:

   bool cmpx(const Coord &a, const Coord &b) { return a.x < b.x; }
   bool cmpy(const Coord &a, const Coord &b) { return a.y < b.y; }
   bool cmpz(const Coord &a, const Coord &b) { return a.z < b.z; }
   bool cmp(const Edge &a, const Edge &b) { return a.c < b.c; }

   각 축에 대해 좌표를 기준으로 행성을 정렬하기 위한 비교 함수와, 간선을 비용 기준으로 정렬하기 위한 비교 함수입니다.

3. **거리 계산 함수**:

   int DISTANCE(const Coord &a, const Coord &b)
   {
       int x=a.x-b.x, y=a.y-b.y, z=a.z-b.z;
       x=x<0?-x:x; y=y<0?-y:y; z=z<0?-z:z;
       if(x > y) x=y; if(x > z) x=z;
       return x;
   }

   두 행성 간의 거리를 계산합니다. 거리 계산은 위에서 언급한 최소 절대값을 기반으로 합니다.

4. **메인 함수**:

   int main()
   {
       int n, v[100000], cnt=1, idx=0;
       scanf("%d", &n);
       for(int i=0;i<n;i++) v[i]=i,c[i].p=i, scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].z);
       std::sort(c,c+n,cmpx);
       for(int i=0;i<n-1;i++,idx++) e[idx].a=c[i].p, e[idx].b=c[i+1].p, 
           e[idx].c=DISTANCE(c[i], c[i+1]);
       std::sort(c,c+n,cmpy);
       for(int i=0;i<n-1;i++,idx++) e[idx].a=c[i].p, e[idx].b=c[i+1].p, 
           e[idx].c=DISTANCE(c[i], c[i+1]);
       std::sort(c,c+n,cmpz);
       for(int i=0;i<n-1;i++,idx++) e[idx].a=c[i].p, e[idx].b=c[i+1].p, 
           e[idx].c=DISTANCE(c[i], c[i+1]);
       std::sort(e,e+idx,cmp);
       long long ans=0;
       for(int i=0; cnt < n; i++)
       {
           int a=e[i].a, b=e[i].b;
           while(v[a]!=a) a=v[a]; while(v[b]!=b) b=v[b];
           if(a==b) continue;
           v[b]=v[e[i].a]=v[e[i].b]=a;
           ans+=e[i].c; cnt++;
       }
       printf("%lld\n", ans);
       return 0;
   }

   - 행성의 수 `n`을 입력받고, 각 행성의 좌표를 입력받습니다.
   - 각 축에 대해 행성을 정렬하고, 인접한 행성 간의 거리를 계산해 간선 리스트를 만듭니다.
   - 생성된 간선 리스트를 거리를 기준으로 정렬한 후, 크루스칼 알고리즘을 통해 최소 스패닝 트리를 구성합니다.
   - 최종적으로 최소 스패닝 트리의 총 비용을 출력합니다.