[Baekjoon] 2887 – 행성 터널

📖 문제 이해하기

이 문제는 N개의 행성을 최소 비용으로 모두 연결하는 터널 네트워크를 구축하는 것입니다. 각 행성은 3차원 공간의 한 점으로 표현되며, 두 행성 사이의 터널 건설 비용은 특별한 방식으로 계산됩니다.

두 행성 A(xA, yA, zA)와 B(xB, yB, zB) 사이의 비용은 min(|x<sub>A</sub>-x<sub>B</sub>|, |y<sub>A</sub>-y<sub>B</sub>|, |z<sub>A</sub>-z<sub>B</sub>|)입니다. 이는 세 좌표축 중에서 가장 작은 거리 차이를 선택한다는 의미입니다. 예를 들어, 행성 A(1, 5, 3)과 행성 B(4, 2, 7) 사이의 비용은 min(|1-4|, |5-2|, |3-7|) = min(3, 3, 4) = 3이 됩니다.

우리의 목표는 정확히 N-1개의 터널을 건설하여 모든 행성이 서로 연결되도록 하면서, 총 건설 비용을 최소화하는 것입니다. 이는 전형적인 최소 신장 트리 문제의 특징입니다.

🧠 첫 번째 시도: 모든 간선을 고려하는 접근법

이 문제를 처음 접했을 때 가장 자연스러운 접근법은 모든 행성 쌍 사이의 거리를 계산하고, 크루스칼 알고리즘이나 프림 알고리즘을 직접 적용하는 것입니다. N개의 행성이 있다면 가능한 모든 간선의 수는 N*(N-1)/2개가 됩니다.

하지만 이 접근법은 심각한 문제를 가지고 있습니다. 행성의 개수 N이 최대 100,000개까지 가능하다는 제약 조건을 고려해보면, 총 간선의 수는 약 50억 개에 달합니다. 이 모든 간선을 생성하고 정렬하는 것만으로도 메모리 부족과 시간 초과가 발생할 수밖에 없습니다. O(N²)의 공간과 시간 복잡도는 현실적으로 불가능합니다.

💡 핵심 아이디어: 차원별 인접 행성만 고려하기

이 문제의 돌파구는 거리 함수의 특별한 성질에서 찾을 수 있습니다. 비용이 min(|xA-xB|, |yA-yB|, |zA-zB|)로 정의되어 있다는 점이 핵심입니다.

만약 어떤 두 행성 사이를 연결하는 최적의 경로가 존재한다면, 그 경로는 반드시 x, y, z 축 중 적어도 하나의 축에서 인접한 행성들을 거쳐야 합니다. 왜냐하면 거리 계산 방식이 세 축 중 최소값을 택하기 때문에, 각 축에서 정렬했을 때 인접하지 않은 행성들을 직접 연결하는 것보다는 중간 행성을 거쳐가는 것이 항상 더 효율적이기 때문입니다.

이러한 관찰로부터 놀라운 최적화가 가능합니다. 모든 행성 쌍을 고려하는 대신, 각 좌표축(x, y, z)에서 정렬했을 때 인접한 행성들 사이의 간선만 고려하면 됩니다. 이렇게 하면 간선의 수를 O(N²)에서 O(N)으로 극적으로 줄일 수 있습니다.

구체적으로 설명하면, x 좌표를 기준으로 행성들을 정렬한 후 인접한 행성들 사이에 간선을 추가합니다. 이때 간선의 가중치는 두 행성 사이의 실제 비용인 min(|x<sub>A</sub>-x<sub>B</sub>|, |y<sub>A</sub>-y<sub>B</sub>|, |z<sub>A</sub>-z<sub>B</sub>|)가 됩니다. y 좌표와 z 좌표에 대해서도 같은 방식으로 간선을 추가합니다.

📘 크루스칼 알고리즘 (Kruskal’s Algorithm)
크루스칼 알고리즘은 최소 신장 트리를 구하는 대표적인 탐욕 알고리즘입니다. 모든 간선을 가중치 순으로 정렬한 후, 사이클을 형성하지 않는 간선들을 차례대로 선택하여 트리를 완성합니다. Union-Find 자료구조를 활용하여 사이클 검사를 효율적으로 수행합니다.

🔍 알고리즘 동작 과정 살펴보기

구체적인 예제를 통해 알고리즘이 어떻게 작동하는지 살펴보겠습니다. 5개의 행성이 다음과 같이 배치되어 있다고 가정해봅시다:

  • 행성 0: (1, 4, 2)
  • 행성 1: (3, 1, 5)
  • 행성 2: (2, 6, 1)
  • 행성 3: (5, 2, 4)
  • 행성 4: (4, 3, 6)

먼저 각 좌표축별로 행성들을 정렬합니다.

  • X 좌표 정렬: [(1,0), (2,2), (3,1), (4,4), (5,3)]
  • Y 좌표 정렬: [(1,1), (2,3), (3,4), (4,0), (6,2)]
  • Z 좌표 정렬: [(1,2), (2,0), (4,3), (5,1), (6,4)]

이제 각 축에서 인접한 행성들 사이의 간선을 생성합니다.

X 축 기준 간선들

  • 행성 0-2: 비용 = min(|1-2|, |4-6|, |2-1|) = min(1, 2, 1) = 1
  • 행성 2-1: 비용 = min(|2-3|, |6-1|, |1-5|) = min(1, 5, 4) = 1
  • 행성 1-4: 비용 = min(|3-4|, |1-3|, |5-6|) = min(1, 2, 1) = 1
  • 행성 4-3: 비용 = min(|4-5|, |3-2|, |6-4|) = min(1, 1, 2) = 1

Y 축과 Z 축에서도 같은 방식으로 간선들을 생성한 후, 모든 간선을 가중치 순으로 정렬합니다. 그 다음 크루스칼 알고리즘을 적용하여 사이클을 형성하지 않는 간선들을 선택합니다.

Union-Find 자료구조를 사용하여 두 행성이 이미 연결되어 있는지(같은 연결 성분에 속하는지) 효율적으로 확인하고, 연결되어 있지 않다면 간선을 추가하여 최소 신장 트리를 구성합니다.

💻 소스 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 100000

int N;
long long X[MAX_N], Y[MAX_N], Z[MAX_N];

<em>// Union-Find의 find 함수: 경로 압축 최적화 적용</em>
int find(vector<int> & p, int x) {
   if (p[x] == -1) return x;  <em>// x가 루트 노드인 경우</em>
   return p[x] = find(p, p[x]);  <em>// 경로 압축: 재귀 호출과 동시에 부모를 루트로 설정</em>
}

<em>// Union-Find의 union 함수: 두 집합을 하나로 합치기</em>
void unite(vector<int> & p, int x, int y) {
   int s1 = find(p, x);  <em>// x가 속한 집합의 루트 찾기</em>
   int s2 = find(p, y);  <em>// y가 속한 집합의 루트 찾기</em>
   p[s1] = s2;  <em>// s1의 부모를 s2로 설정하여 두 집합 합치기</em>
}

int main()
{
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   
   cin >> N;
   <em>// N개 행성의 좌표 입력받기</em>
   for (int i = 0; i < N; ++i) {
      cin >> X[i] >> Y[i] >> Z[i];
   }
   
   <em>// 각 좌표축별로 (좌표값, 행성번호) 쌍을 저장할 벡터 생성</em>
   vector<pair<int,int>> x, y, z;
   for (int i = 0; i < N; ++i) {
      x.push_back({X[i], i});  <em>// x좌표와 행성 인덱스를 쌍으로 저장</em>
      y.push_back({Y[i], i});  <em>// y좌표와 행성 인덱스를 쌍으로 저장</em>
      z.push_back({Z[i], i});  <em>// z좌표와 행성 인덱스를 쌍으로 저장</em>
   }
   
   <em>// 각 좌표축별로 정렬: 좌표값을 기준으로 오름차순 정렬</em>
   sort(x.begin(), x.end());
   sort(y.begin(), y.end());
   sort(z.begin(), z.end());
   
   <em>// 모든 후보 간선들을 저장할 벡터: (비용, 행성1, 행성2)</em>
   vector<tuple<long long, int, int>> A;
   
   <em>// 각 좌표축에서 인접한 행성들 사이의 간선 생성</em>
   for (int i = 1; i < N; ++i) {
      <em>// x축에서 인접한 두 행성 사이의 실제 연결 비용 계산</em>
      int planet1 = x[i].second;    <em>// 현재 행성의 인덱스</em>
      int planet2 = x[i-1].second;  <em>// 이전 행성의 인덱스</em>
      long long cost = min({abs(X[planet1] - X[planet2]), 
                           abs(Y[planet1] - Y[planet2]), 
                           abs(Z[planet1] - Z[planet2])});
      A.push_back(make_tuple(cost, planet1, planet2));
      
      <em>// y축에서 인접한 두 행성 사이의 실제 연결 비용 계산</em>
      planet1 = y[i].second;
      planet2 = y[i-1].second;
      cost = min({abs(X[planet1] - X[planet2]), 
                  abs(Y[planet1] - Y[planet2]), 
                  abs(Z[planet1] - Z[planet2])});
      A.push_back(make_tuple(cost, planet1, planet2));
      
      <em>// z축에서 인접한 두 행성 사이의 실제 연결 비용 계산</em>
      planet1 = z[i].second;
      planet2 = z[i-1].second;
      cost = min({abs(X[planet1] - X[planet2]), 
                  abs(Y[planet1] - Y[planet2]), 
                  abs(Z[planet1] - Z[planet2])});
      A.push_back(make_tuple(cost, planet1, planet2));
   }
   
   <em>// 크루스칼 알고리즘: 모든 간선을 비용 순으로 정렬</em>
   sort(A.begin(), A.end());
   
   <em>// Union-Find 초기화: -1은 해당 노드가 루트임을 의미</em>
   vector<int> p(N, -1);
   int cnt = 0;      <em>// 현재까지 선택한 간선의 개수</em>
   int idx = 0;      <em>// 현재 검사 중인 간선의 인덱스</em>
   long long d, u, v; <em>// 간선의 비용과 연결하는 두 행성</em>
   long long ans = 0; <em>// 최소 신장 트리의 총 비용</em>
   
   <em>// 정확히 N-1개의 간선을 선택할 때까지 반복</em>
   while(cnt < N-1) {
      tie(d, u, v) = A[idx++];  <em>// 다음 최소 비용 간선 선택</em>
      
      <em>// 두 행성이 이미 연결되어 있다면(같은 연결 성분) 건너뛰기</em>
      if (find(p, u) == find(p, v)) continue;
      
      <em>// 두 행성을 연결하고 비용 누적</em>
      unite(p, u, v);
      ans += d;
      cnt++;  <em>// 선택한 간선 개수 증가</em>
   }
   
   cout << ans << "\n";  <em>// 최종 최소 비용 출력</em>
   return 0;
}

🔁 대안적 접근법: 프림 알고리즘

이 문제는 프림 알고리즘으로도 해결할 수 있습니다. 프림 알고리즘은 임의의 시작점에서 시작하여 현재 트리에 인접한 간선 중 최소 비용 간선을 반복적으로 선택하는 방식입니다. 하지만 이 경우에도 모든 간선을 미리 생성해야 하므로 동일한 최적화 기법이 필요합니다.

크루스칼 알고리즘이 이 문제에 더 적합한 이유는 간선 중심의 접근법이기 때문입니다. 우리가 생성하는 O(N) 개의 후보 간선들을 한 번에 정렬한 후 처리할 수 있어서 구현이 더 직관적입니다.

📌 핵심 개념과 교훈

이 문제의 핵심은 문제의 특수한 구조를 파악하여 검색 공간을 극적으로 줄이는 것이었습니다. 단순히 최소 신장 트리 알고리즘을 아는 것만으로는 부족했고, 거리 함수의 특성을 분석하여 필요한 간선만 생성하는 통찰이 필요했습니다.

특히 min(|xA-xB|, |yA-yB|, |zA-zB|) 형태의 거리 함수에서는 각 차원별로 정렬된 순서에서 인접한 원소들만 고려하면 충분하다는 것이 핵심 아이디어였습니다. 이를 통해 O(N²) 복잡도를 O(N log N)으로 줄일 수 있었습니다.

Similar Posts