[백준/C++] 2887번. 행성 터널

[백준/C++] 1516번. 게임 개발

1. 문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

3. 출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

4. 풀이

• 최소 신장 트리 문제
• 행성의 정보를 입력 받는다.
• 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이기 때문에 x, y, z를 각각 배열로 만들어 준다.
• 각 배열을 정렬하고 비용을 구해서x[i+1].first - x[i].first edges배열에 삽입한다.
• edges 배열을 정렬하고 사이클이 있는지 확인하면서 최단 거리를 구한다.

5. 처음 코드와 달라진 점

• x, y, z를 따로 해주지 않고 모든 경우의 수를 구해서 메모리 초과가 났다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int parent[1000001];
vector<pair<int, pair<int, int> > > edges;

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

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


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

  cin>>n;

  for (int i = 0; i < n; i++) {
    parent[i] = i;
  }
  
  vector<pair<int, int> > x;
  vector<pair<int, int> > y;
  vector<pair<int, int> > z;

  for (int i = 0; i < n; i++) {
    int a, b, c;
    cin>>a>>b>>c;

    x.push_back(make_pair(a, i));
    y.push_back(make_pair(b, i));
    z.push_back(make_pair(c, i));
  }

  sort(x.begin(), x.end());
  sort(y.begin(), y.end());
  sort(z.begin(), z.end());

  for (int i = 0; i < n - 1; i++) {
    edges.push_back(make_pair(x[i+1].first - x[i].first, make_pair(x[i].second, x[i+1].second)));
    edges.push_back(make_pair(y[i+1].first - y[i].first, make_pair(y[i].second, y[i+1].second)));
    edges.push_back(make_pair(z[i+1].first - z[i].first, make_pair(z[i].second, z[i+1].second)));
  }

  sort(edges.begin(), edges.end());
  
  int answer = 0;
  for (int i = 0; i < edges.size(); i++) {
    int a, b, cost;
    cost = edges[i].first;
    a = edges[i].second.first;
    b = edges[i].second.second;

    if(findParent(a) != findParent(b)) {
      answer += cost;
      unionParent(a, b);
    }
  }

  cout<<answer;
}