[백준] 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;
}