[백준] 2887 행성 터널
문제
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)
터널을 총 N-1개 건설해서 모든 행성이 서로 연결하기 위해 필요한 최소비용
입력
행성의 개수 N(1 ≤ N ≤ 100,000)
각 행성의 x, y, z좌표(-10^9보다 크거나 같고, 10^9보다 작거나 같은 정수)
출력
모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력
풀이
N개의 행성을 N-1개의 터널로 연결하기 위한 최소 비용 구하는 문제이기 때문에 최소 신장 트리(MST) 문제로 풀 수 있다.
FindParent 함수는 각 행성의 부모 노드를 찾는 함수이고, Union 함수는 두 개의 행성의 부모노드가 다른 경우 MST에 추가(합치는)하는 함수
1) 메모리 초과
3차원 좌표로 주어지기 때문에 처음에는 우선 3개의 정보를 담을 수 있도록 구조체로 구현해보았다. 하지만 계속해서 메모리 초과가 되었고, 3개의 정보를 담는 tuple을 이용한 벡터도 사용했지만 마찬가지였다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <stdlib.h>
#include<tuple>
#define MAXN 100001
using namespace std;
int N;
struct planet {
int x;
int y;
int z;
};
vector<tuple<int, int, int> > cost;
planet planets[MAXN];
int parents[MAXN];
int FindParent(int x) {
if (parents[x] == x) {
return x;
}
return parents[x] = FindParent(parents[x]);
}
void Union(int x, int y) {
x = FindParent(x);
y = FindParent(y);
parents[x] = y;
FindParent(x);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
parents[i] = i;
}
int a, b, c;
for (int i = 0; i < N; i++) {
cin >> a >> b >> c;
planets[i].x = a;
planets[i].y = b;
planets[i].z = c;
if (i > 0) {
for (int j = i - 1; j >= 0; j--) {
int d = min({abs(a - planets[j].x), abs(b - planets[j].y), abs(c - planets[j].z) });
cost.push_back(make_tuple(d,j,i));
}
}
}
sort(cost.begin(), cost.end());
long long result = 0;
for (int i = 0; i < cost.size(); i++) {
if (FindParent(get<1>(cost[i])) != FindParent(get<2>(cost[i]))) {
result += get<0>(cost[i]);
Union(get<1>(cost[i]), get<2>(cost[i]));
}
else {
continue;
}
}
cout << result << "\n";
return 0;
}
2) 성공
알고리즘참고링크
다른 풀이들을 참고해보니 한 번에 3개를 저장하여 정렬하는 것이 아닌, X,Y,Z 각각을 따로 저장하여 정렬한 후 앞에서부터 조건을 해당하는 N-1만큼의 터널을 선택하는 것으로 푸니 해결되었다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<tuple>
#include<cmath>
#define MAXN 100001
using namespace std;
int N;
vector<tuple<int, int, int> > cost;
vector<pair<int, int>> X, Y, Z;
int parents[MAXN];
int FindParent(int x) {
if (parents[x] == x) {
return x;
}
return parents[x] = FindParent(parents[x]);
}
void Union(int x, int y) {
x = FindParent(x);
y = FindParent(y);
parents[x] = y;
FindParent(x);
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
parents[i] = i; //부모배열 자기자신으로 초기화
}
int a, b, c;
for (int i = 0; i < N; i++) {
cin >> a >> b >> c;
X.push_back({ a,i });
Y.push_back({ b,i });
Z.push_back({ c,i });
}
//X,Y,Z값 각각 오름차순 정렬
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
sort(Z.begin(), Z.end());
for (int i = 0; i < N - 1; i++) {
cost.push_back({ X[i + 1].first - X[i].first,X[i].second, X[i + 1].second });
cost.push_back({ Y[i + 1].first - Y[i].first,Y[i].second,Y[i + 1].second });
cost.push_back({ Z[i + 1].first - Z[i].first,Z[i].second, Z[i + 1].second });
}
sort(cost.begin(), cost.end()); //거리에 따라 오름차순 정렬
long long result = 0;
int count = 0; //N-1도로만큼 추가
for (int i = 0; i < cost.size(); i++) {
if (FindParent(get<1>(cost[i])) != FindParent(get<2>(cost[i]))) {
result += get<0>(cost[i]);
count++;
Union(get<1>(cost[i]), get<2>(cost[i]));
}
if (count == N-1) {
break;
}
}
cout << result << "\n";
return 0;
}
Author And Source
이 문제에 관하여([백준] 2887 행성 터널), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@botong_99/백준-2887-행성터널저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)