취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2887번 문제인 행성 터널이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2887

이 문제에서는, 3차원 좌표에 주어진 N개의 행성들을 모두 이을 수 있는 터널을 만드는 것이 목표이다.

이 문제는 각 N개의 행성들을 그래프의 노드라고 생각하고, 서로 다른 두 행성 사이에 두 행성 사이 거리를 가중치로 갖는 간선이 있는 완전그래프에서 MST(최소신장트리)를 찾는 문제로 생각할 수 있다.

단, 노드의 개수가 최대 10만개까지 가능하므로, 모든 서로 다른 두 행성을 잇는 간선을 생각할 수는 없고(시간 면으로나 메모리 면으로나), MST에 쓰일 수 있는 간선의 후보를 잘 추려내야한다.

다음과 같은 관찰을 하자.

N개의 행성 중, 세 행성 p1, p2, p3가 대하여 x좌표가 오름차순으로 주어져있는 상황을 생각해보자.

이 상황에서, p1, p2 사이의 x좌표의 차가 p1, p2 사이의 거리이고 p2, p3 사이의 x좌표의 차가 p2, p3 사이의 거리이면 p1과 p3를 잇는 간선은 MST에 쓰일 수 없다. 그 증명은 다음과 같다:

p1과 p3을 잇는 간선이 spanning tree에 포함되어있다고 가정하자. 이 spanning tree에서 p1과 p3을 잇는 간선을 지운다면 MST는 두개의 connected component로 분리되게 된다. 이 때, p2는 p1이 포함되어 있는 component와 연결되어있거나 p3이 포함되어 있는 component와 연결되어있다. 각각의 경우 p2와 p3 / p2와 p1을 잇는 간선을 그으면 기존 spanning tree보다 더 적은 총합 가중치를 가진 spanning tree를 만들 수 있다.

위와 같은 증명과 같은 아이디어를 바탕으로, MST에 사용될 수 있는 후보 간선은 x좌표, y좌표, z좌표 순으로 정렬했을 때 서로 인접한 순서에 있는 노드를 잇는 에지들일 것임을 알 수 있다.

이 추려진 (최대 30만개의) 후보간선들을 이용하여 MST를 구하는 Kruskal(크루스칼) 알고리즘을 이용하면 문제를 해결할 수 있다.

아래 구현 코드에서, (예를 들어) x좌표를 기준으로 정렬된 인접한 두 노드를 잇는 간선을 후보간선으로 넣을 때 거리를 실제 거리 대신 두 노드의 x좌표의 차를 이용하고 있는데, 이렇게 구현해도 되는 이유는 실제 거리가 x좌표의 차가 아니면서 실제 MST 중 하나의 구성 에지라면 두 노드 사이의 거리를 구하게 되는 방향의 축으로 정렬할 때 인접하게 될 것이기 때문이다. (위의 "관찰의 증명"을 생각해보자.) 이 설명은 x를 y 또는 z로 바꿔도 마찬가지로 통한다.

아래는 제출한 소스코드이다.

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

struct P {
	int x, y, z;
	int idx;
};

struct E {
	long long w;
	int idx1, idx2;
};

bool cmpx(P p1, P p2) {
	if (p1.x < p2.x) return 1;
	else return 0;
}

bool cmpy(P p1, P p2) {
	if (p1.y < p2.y) return 1;
	else return 0;
}

bool cmpz(P p1, P p2) {
	if (p1.z < p2.z) return 1;
	else return 0;
}

bool cmpw(E e1, E e2) {
	if (e1.w < e2.w) return 1;
	else return 0;
}

int dset[100000];

int findf(int x) {
	if (x == dset[x]) return x;
	else return dset[x] = findf(dset[x]);
}

P arr[100000];
vector<E> edge;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;

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

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

	sort(arr, arr + N, cmpx);
	for (int i = 1; i < N; i++) {
		E e;
		e.w = arr[i].x - arr[i - 1].x;
		e.idx1 = arr[i].idx;
		e.idx2 = arr[i - 1].idx;
		edge.push_back(e);
	}
	sort(arr, arr + N, cmpy);
	for (int i = 1; i < N; i++) {
		E e;
		e.w = arr[i].y - arr[i - 1].y;
		e.idx1 = arr[i].idx;
		e.idx2 = arr[i - 1].idx;
		edge.push_back(e);
	}
	sort(arr, arr + N, cmpz);
	for (int i = 1; i < N; i++) {
		E e;
		e.w = arr[i].z - arr[i - 1].z;
		e.idx1 = arr[i].idx;
		e.idx2 = arr[i - 1].idx;
		edge.push_back(e);
	}

	sort(edge.begin(), edge.end(), cmpw);

	long long ans = 0;
	for (auto e : edge) {
		int x = findf(e.idx1), y = findf(e.idx2);
		if (x == y) continue;
		dset[y] = x;
		ans += e.w;
	}

	cout << ans;
}