백준 2887 : 행성 터널

행성 터널 성공다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

15037

5586

3916

35.535%

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

예제 입력 1 복사

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

예제 출력 1 복사

4

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #7 4번

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 그래프 이론
• 정렬
• 최소 스패닝 트리

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
	int cost,x, y;
};
int parent[100001];
int n;
vector<pair<int, int>> x;
vector<pair<int, int>> y;
vector<pair<int, int>> z;
vector<info> graph;
bool cmp(info a, info b) {
	return a.cost < b.cost;
}

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

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x != y)
		parent[y] = x;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)parent[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 });
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	sort(z.begin(), z.end());

	for (int i = 0; i < n - 1; i++) {
		graph.push_back({ x[i + 1].first - x[i].first, x[i].second,x[i + 1].second });
		graph.push_back({ y[i + 1].first - y[i].first, y[i].second,y[i + 1].second });
		graph.push_back({ z[i + 1].first - z[i].first, z[i].second,z[i + 1].second });
	}
	sort(graph.begin(), graph.end(),cmp);
	int answer=0;

	for (int i = 0; i < graph.size(); i++) {
		int x = graph[i].x;
		int y = graph[i].y;
		int cost = graph[i].cost;
		if (Find(x) != Find(y)) {
			Union(x, y);
			answer += cost;
		}
	}

	cout << answer;

	return 0;
}

드디어 플레티넘문제를 풀었다. 느리지만 한걸음 한걸음 성장하는 기분이 들어서 좋다. 온전히 실력으로 풀었다기보단 사실 검색의 도움을 좀 받았다. 

10만개의 노드가 주어지기때문에 일일이 가중치를 계산하면 10만 곱하기 10만 100억번의 연산을 해야하는데, 시간초과날것이 분명하기에 어떻게 연산을 줄여줄지를 몰라서 생각을 오래했다.

그래서 인터넷에서 찾았는데 만약 x의 좌표만 따로 빼서 11,3,2,8이라는 숫자를 얻으면 이를 소팅해서

2 3 8 11로 만들면 바로 옆에 것들과 비교해주면 된다. 이는  O(n)으로 계산이 가능하다.

나머지는 서로소 집합과 크루스칼 알고리즘을 기본만 활용하면 되는 문제이다.

플래티넘부터는 수학적 배경이 요구된다는 데 어느정도 맞는 말 같다.

그리고 오늘부터 면접 준비를 위해 알고리즘보단 현재 it 시사에 대한 공부를 해서 포스팅 해볼까한다.