2887 - 행성 터널

첫번째 풀이

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

vector<pair<int,pair<int, int>>> v;

struct K {
	int x, y, z;
} arr[100000];
int N;
int parent[100000];
int ans;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i].x >> arr[i].y >> arr[i].z;
	}

	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}
}

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

void unionNode(int a, int b) {
	if (a > b)swap(a, b);
	parent[getParent(b)] = getParent(a); // b의 부모가 a가 되어야한다
}
void run() {
	for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			int dis_x = abs(arr[i].x - arr[j].x);
			int dis_y = abs(arr[i].y - arr[j].y);
			int dis_z = abs(arr[i].z - arr[j].z);
			int distance = min(dis_x, min(dis_y, dis_z));
			v.push_back({ distance, {i, j} });
		}
	}
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		int a = v[i].second.first;
		int b = v[i].second.second;
		int distance = v[i].first;
		if (getParent(a) != getParent(b)) {
			ans += distance;
			unionNode(a, b);
		}
	}
	cout << ans;
}

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

	Input();
	run();
	
	return 0;
}

메모리 초과!
문제에서 주어진 메모리 제한은 128 MB인데 밑의 코드 부분에서 N의 최댓값이 100,000이므로 벡터v에 들어가는 크기는 10,000,000,000(10,000MB)이므로 메모리 초과가 난다.
밑의 코드를 효율적으로 바꿔야합니다.

for (int i = 0; i < N - 1; i++) {
		for (int j = i + 1; j < N; j++) {
			int dis_x = abs(arr[i].x - arr[j].x);
			int dis_y = abs(arr[i].y - arr[j].y);
			int dis_z = abs(arr[i].z - arr[j].z);
			int distance = min(dis_x, min(dis_y, dis_z));
			v.push_back({ distance, {i, j} });
		}
	}

---

맞은 풀이

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

vector<pair<int,pair<int, int>>> v;

struct K {
	int x, y, z;
} arr[100000];
int N;
int parent[100000];
int ans;
vector<pair<int, int>>X;
vector<pair<int, int>>Y;
vector<pair<int, int>>Z;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		X.push_back({ x,i });
		Y.push_back({ y,i });
		Z.push_back({ z,i });
	}

	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}
}

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

void unionNode(int a, int b) {
	if (a > b)swap(a, b);
	parent[getParent(b)] = getParent(a); // b의 부모가 a가 되어야한다
}
void run() {
	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	sort(Z.begin(), Z.end());
	for (int i = 0; i < N - 1; i++) {
		v.push_back({ X[i + 1].first - X[i].first , {X[i].second, X[i + 1].second} });
		v.push_back({ Y[i + 1].first - Y[i].first , {Y[i].second, Y[i + 1].second} });
		v.push_back({ Z[i + 1].first - Z[i].first , {Z[i].second, Z[i + 1].second} });
	}
	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		int a = v[i].second.first;
		int b = v[i].second.second;
		int distance = v[i].first;
		if (getParent(a) != getParent(b)) {
			ans += distance;
			unionNode(a, b);
		}
	}
	cout << ans;
}

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

	Input();
	run();
	
	return 0;
}

도저히 아이디어가 생각나지 않아서 풀이를 봤다
최솟 값은 항상 min(|xA-xB|, |yA-yB|, |zA-zB|) 여기에서 발생하므로 최솟 값이 될수 있는 후보들만 벡터v에 넣어두고 그것들만 비교하며 최소 신장 트리를 만들면 O(3N)의 시간 복잡도로 문제를 해결할 수 있었다. (전의 풀이의 시간복잡도 : O(N^2))

sort(X.begin(), X.end()); // x좌표끼리 정렬
sort(Y.begin(), Y.end()); // y좌표끼리 정렬
sort(Z.begin(), Z.end()); // z좌표끼리 정렬

for (int i = 0; i < N - 1; i++) {
// 차이가 가장 작은 것들을 넣는다
	info.push_back({ X[i + 1].first - X[i].first , {X[i].second, X[i + 1].second} });
	info.push_back({ Y[i + 1].first - Y[i].first , {Y[i].second, Y[i + 1].second} });
	info.push_back({ Z[i + 1].first - Z[i].first , {Z[i].second, Z[i + 1].second} });
}