[백준] 2887 - 행성 터널

[링크] https://www.acmicpc.net/problem/2887

💎 문제 조건과 설명

문제 조건과 설명은 위의 링크를 참조 부탁드립니다.

🚀 생각한 아이디어

이 문제는 크루스칼 알고리즘을 구현하는 문제입니다.

크루스칼 알고리즘은 각 정점 간 간선의 가중치를 작은 순서대로 선택해 나가는데, union-find 연산으로 싸이클이 발생하는지 여부를 판단하면서 선택하는 것이 주요 구현 내용입니다.

여기서 선택의 대상인 간선의 가중치 값은, 문제에서 주어진 각 행성들 간의 X, Y, Z 좌표 차이 중 최솟값 이 됩니다. 그러므로 문제에서 간선의 가중치가 될 수 있는 이 값을 찾아놓는 것이 핵심입니다.

처음에는 모든 행성들 간에 서로 X, Y, Z 좌표값 차이를 구해서 간선의 가중치 정보로 넣는 방법을 생각할 수 있지만, 이 문제에서는 행성이 최대 10만개 주어지므로 대략 10만*10만 만큼의 비교 및 데이터가 발생합니다. 따라서 메모리 초과 문제가 발생할 수 있습니다.

어차피 행성들 간의 X, Y, Z 좌표값 차이 중 가장 작은 값들이 간선 가중치 후보가 될 수 있는 것이므로 아래와 같은 방법을 생각할 수 있습니다.

각 행성들의 X,Y,Z 좌표를 별도로 벡터에 담아두고 오름차순 정렬해 놓는다.
X 좌표를 우선 예로 들면, 행성 A. B, C, D 의 X좌표가 각각 11, 3, 2, 8 이었을 경우 오름차순 정렬하면 2, 3, 8, 11 이며, 각각 C, B, D, A 순이다.
따라서 행성 C-B, B-D, D-A 로 연결될 때 각각의 X좌표 차이(3-2, 8-3, 11-8)가 행성들 간 X좌표 차이의 최솟값이 된다.
즉, 행성 C는 B와 연결될 때 X좌표 차이가 가장 작으며, 행성 B는 행성 D와 연결될 때 X좌표 차이가 가장 작다.
Y, Z 좌표에도 위와 똑같은 방법을 적용한다. 그리고 구해진 X, Y, Z 좌표 차이의 최솟값들 모음을 가지고 크루스칼 알고리즘을 진행한다.

🚀 소스코드(C++)

#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <map>

#define pii pair<int, int>

using namespace std;

vector<pair<int, int>> X;
vector<pair<int, int>> Y;
vector<pair<int, int>> Z;

vector<pair<int, pii>> info;
int parent[100001];

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

void unite(int a, int b) {
	a = find(a);
	b = find(b);

	if (a < b) parent[b] = a;
	else parent[a] = b;
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

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

	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 });
	}

	sort(X.begin(), X.end());
	sort(Y.begin(), Y.end());
	sort(Z.begin(), Z.end());

	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} });
	}

	sort(info.begin(), info.end());

	int cnt = 0;
	int total = 0;

	for (int i = 0; i < info.size(); i++) {
		int a = info[i].second.first;
		int b = info[i].second.second;
		int val = info[i].first;

		if (find(a) != find(b)) {
			unite(a, b);
			total += val;
		}
	}

	cout << total;

	return 0;
}

[백준] 2887 - 행성 터널