백준 알고리즘 2887번 : 행성 터널

링크

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

문제

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

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

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

입력

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

출력

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

예제 입력 및 출력

풀이 코드(C++)

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define MAX 1005
#define INF 1e9+7
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double; 
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdbl = pair<double, double>;
using vi = vector<int>;
using tiii = tuple<int,int,int>;
#define sz(a) int((a).size())

struct UnionFind {
	vector<int> parent, rank, cnt;
	UnionFind(int n) : parent(n), rank(n, 1), cnt(n, 1) {
		iota(parent.begin(), parent.end(), 0);
	}
	int Find(int x) {
		return x == parent[x] ? x : parent[x] = Find(parent[x]);
	}
	bool Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return 0;
		if (rank[a] < rank[b]) swap(a, b);
		parent[b] = a;
		rank[a] += rank[a] == rank[b];
		cnt[a] += cnt[b];
		return 1;
	}
};

struct Edge{
  int u,v,w;
  Edge(int u1,int v1,int w1):u(u1),v(v1),w(w1){}
  bool operator < (const Edge& O) const{ return w < O.w;}
};

struct Point3d{
  int x; int y; int z; int idx;
};

int find_dist(Point3d a, Point3d b,int c){
  if(c == 1) return abs(a.x - b.x);
  else if(c == 2) return abs(a.y - b.y);
  return abs(a.z - b.z);
}

bool cmpX(Point3d a, Point3d b){
  return a.x < b.x;
}

bool cmpY(Point3d a, Point3d b){
  return a.y < b.y;
}

bool cmpZ(Point3d a, Point3d b){
  return a.z < b.z;
}

int32_t main(){
  fastio;
  int n,sum = 0,cnt = 0; cin >> n;
  vector<Edge> e;
  vector<Point3d> coord(n);
  for(int i = 0; i < n; i++){
    cin >> coord[i].x >> coord[i].y >> coord[i].z; 
    coord[i].idx = i;
  }
  // x기준 간선
  sort(coord.begin(), coord.end(), cmpX);
  for(int i = 0; i < n - 1; i++){
    int c = find_dist(coord[i], coord[i + 1],1);
    e.pb(Edge(coord[i].idx,coord[i + 1].idx, c));
  }
  // y기준 간선
  sort(coord.begin(), coord.end(), cmpY);
  for(int i = 0; i < n - 1; i++){
    int c = find_dist(coord[i], coord[i + 1],2);
    e.pb(Edge(coord[i].idx,coord[i + 1].idx, c));
  }
  // z기준 간선
  sort(coord.begin(), coord.end(), cmpZ);
  for(int i = 0; i < n - 1; i++){
    int c = find_dist(coord[i], coord[i + 1],3);
    e.pb(Edge(coord[i].idx,coord[i + 1].idx, c));
  }
  sort(e.begin(), e.end());
  UnionFind UF(n+1);
  for(int i = 0; ; i++){
    if(UF.Union(e[i].u, e[i].v)){
      sum += e[i].w;
      if(++cnt == n - 1) break;
    }
  }
  cout << sum << "\n";
  return 0;
}

풀이법

n이 최대 10만개까지 입력으로 주어지기 때문에 naive하게 크루스칼을 진행하면 메모리 초과가 납니다
실패코드

문제의 조건에서 행성 간 터널의 길이를 구하는 식을 잘 보면 필요한 간선의 수는 n^2에서 3n까지 줄일 수 있습니다.
MST를 만들기 위해선 모든 간선이 필요한게 아니라 각 정점들이 최소비용으로 연결이 되어있으면 되기 때문에 최소 비용으로 각 행성을 연결할 때 필요한 간선들만 만들어주면 됩니다.

즉, 각 좌표별로 정렬을 한 후에 i번째 행성과 i + 1번째 행성간의 각 좌표별로 간선을 만들어주면 필요한 간선을 얻을 수 있습니다.

이후 크루스칼 알고리즘을 활용해서 MST를 구해주면 됩니다.

채점 현황