[백준/BOJ] 2887 행성 터널 - 접근과 풀이 (c++)

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

2887번: 행성 터널

MST 응용 문제

---

접근 방법

 

처음에는 가중치를 구하는 방법만 다른 MST 문제인 줄 알고 그냥 풀었다.

그러나 좌표들 사이의 가중치를 구하려면 O(N^2)의 시간과 공간이 필요한데, N이 10만이라서 다시 생각했다.

 

대충 정렬을 활용해야 한다는 것은 쉽게 떠올렸으나, 어떻게 사용해야 할지 감이 안왔다. 

 

그래서 풀이를 보았다. 이 곳에 설명이 상세하게 되어있다.

 

아래는 gmldnjs526님의 댓글인데, 이해가 잘 되는 댓글이다.

다만 3차원 공간에서 터널의 길이가 일반적인 방법으로 생각하는 길이가 아니어서 직관적인 이해가 상당히 힘들었다.

정답을 구성하는 터널 N-1개 중에서 어떤 한 터널을 택해서 해당 터널이 잇는 행성을 P, Q라고 하자.
정의에 의해 해당 터널의 길이는 |xP-xQ|, |yP-yQ|, |zP-zQ| 중 가장 작은 값이다.

|xP-xQ|가 해당 터널의 길이인 경우,
만약 어떤 한 행성 M의 x좌표 xM이 xP와 xQ 사이의 값이라면 다음과 같은 과정을 통해 정답보다 전체 비용 합이 더 작은 조합을 만들 수 있다.
(정답이 정답이 아님, 모순)

1. P, Q를 잇는 해당 터널을 제거한다.
전체 비용은 |xP-xQ| 감소하며, Spanning Tree에서 간선 하나를 제거한 것이므로 M은 P와 Q 중에 하나와는 연결되어 있고 다른 하나와는 연결되어 있지 않게 된다.
처음에 P, Q를 정하는 순서를 임의로 정할 수 있으므로 이때 M과 연결되어 있지 않은 행성을 P라고 하자.

2. P와 M 사이에 터널을 새로 건설한다.
정의에 의해 새로 건설한 터널의 길이는 min(|xP-xM|, |yP-yM|, |zP-zM|) 이므로 |xP-xM| 이하이다.
건설 후 Spanning Tree 조건을 만족하게 되어 다시 모든 행성이 서로 연결되며, |xP-xM| < |xP-xQ| 이므로 전체 비용 합은 처음의 정답보다 더 작아진다.

|yP-yQ|가 해당 터널의 길이인 경우,
|zP-zQ|가 해당 터널의 길이인 경우도 동일한 과정으로 모순이 도출된다.

따라서 정답을 구성하는 터널이 존재하는 축을 기준으로 봤을 때 터널로 이어지는 두 행성 사이에는 다른 행성이 존재해선 안된다.

 

---

풀이

 

tag : mst

 

#include<iostream>
#include<vector>
#include<algorithm>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int N;
int x, y, z;
pii v[3][100003]; //xyz좌표와 idx
int parent[100002];
vector<pair<int, pii>> edges; // cost, idx1 idx2
int findPr(int idx){
  if(parent[idx]!=idx)
    return findPr(parent[idx]);
  return idx;
}
void unionPr(int idx1,int idx2){
  int pr1 = findPr(idx1);
  int pr2 = findPr(idx2);
  if(pr1<pr2)
    parent[pr2] = pr1;
  else
    parent[pr1] = pr2;
}
int main(){
  cin>>N;
  for (int i = 0; i < N;i++){
    parent[i] = i;
    cin >> x >> y >> z;
    v[0][i] = mp(x, i);
    v[1][i] = mp(y, i);
    v[2][i] = mp(z, i);
  }
  sort(v[0], v[0] + N);
  sort(v[1], v[1] + N);
  sort(v[2], v[2] + N);

  for (int i = 0; i < 3;i++){
    for (int j = 0; j < N-1;j++){
      int cost = abs(v[i][j].first - v[i][j+1].first);
      int idx1 = v[i][j].second;
      int idx2 = v[i][j+1].second;
      edges.push_back(mp(cost, mp(idx1, idx2)));
    }
  }
  sort(edges.begin(), edges.end());
  int ans = 0;
  int cnt = 0;
  for (int i = 0; i < edges.size();i++){
    int pr1 = findPr(edges[i].second.first);
    int pr2 = findPr(edges[i].second.second);
    if(pr1==pr2) //사이클
      continue;
    ans += edges[i].first;
    unionPr(edges[i].second.first, edges[i].second.second);
    cnt++;
    if(cnt==N-1)
      break;
  }
  cout << ans;
}