백준 알고리즘 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를 구해주면 됩니다.
채점 현황
Author And Source
이 문제에 관하여(백준 알고리즘 2887번 : 행성 터널), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inwooleeme/백준-알고리즘-2887번-행성-터널저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)