728x90
반응형
링크
https://www.acmicpc.net/problem/2887
2887번: 행성 터널
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이
www.acmicpc.net
해설
최소 신장 트리 문제입니다.
그런데 다른 문제들과는 조금 다르게 모든 노드들이 다 연결되어있는 상태라
기존의 방법대로 kruskal 알고리즘을 적용시키면 약 N^2 개의 공간이 필요해서 메모리 초과가 됩니다.
이 문제의 특징은 x y z 축의 값중 가장 작은 값이 최소 비용이 된다는 것입니다.
즉 kruskal 알고리즘을 적용할 때 모든 노드를 볼 필요가 없고 근처에 있는 후보가 될만한 것들 만 골라서
적용시켜야 합니다.
이 근처에 있는 후보들을 뽑는 방법이 각 축에 대해 정렬하게되면 바로 옆에 있는 노드들이 후보가 되게 됩니다.
각 축에 대해 후보들을 모두 뽑아서 kruskal 알고리즘을 적용하면 됩니다.
아래 코드에 모두 구현되어있습니다.
코드
#include <iostream> #include <queue> #include <algorithm> using namespace std; struct edge { int len, a, b; }; bool operator < (edge& _a, edge& _b) { return _a.len < _b.len; } struct xyz { int x, y, z, idx; }; bool comp_x(xyz _a, xyz _b) { return _a.x < _b.x; } bool comp_y(xyz _a, xyz _b) { return _a.y < _b.y; } bool comp_z(xyz _a, xyz _b) { return _a.z < _b.z; } int N, DIST = 0, parent[100000], set_size[100000]; xyz TABLE[100000]; int abs(int _a) { if (_a < 0) return -_a; return _a; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 0; i < N; ++i) { cin >> TABLE[i].x >> TABLE[i].y >> TABLE[i].z; TABLE[i].idx = i; parent[i] = i; set_size[i] = 1; } vector<edge> list; list.reserve(N * 3); sort(TABLE, TABLE + N, comp_x); for (int i = 1; i < N; ++i) list.push_back({ abs(TABLE[i].x - TABLE[i-1].x), TABLE[i].idx, TABLE[i - 1].idx }); sort(TABLE, TABLE + N, comp_y); for (int i = 1; i < N; ++i) list.push_back({ abs(TABLE[i].y - TABLE[i - 1].y), TABLE[i].idx, TABLE[i - 1].idx }); sort(TABLE, TABLE + N, comp_z); for (int i = 1; i < N; ++i) list.push_back({ abs(TABLE[i].z - TABLE[i - 1].z), TABLE[i].idx, TABLE[i - 1].idx }); sort(list.begin(), list.end()); for (int i = 0; i < list.size(); ++i) { int left_p = list[i].a, right_p = list[i].b; while (left_p != parent[left_p]) left_p = parent[left_p]; while (right_p != parent[right_p]) right_p = parent[right_p]; if (left_p == right_p) continue; if (set_size[left_p] > set_size[right_p]) swap(left_p, right_p); parent[left_p] = right_p; DIST += list[i].len; set_size[right_p] += set_size[left_p]; if (set_size[right_p] == N) break; } cout << DIST; return 0; }
728x90
반응형
'컴퓨터공학 > 백준' 카테고리의 다른 글
[백준][4195][C++] 친구 네트워크 (0) | 2021.07.17 |
---|---|
[백준][14003][C++] 가장 긴 증가하는 부분 수열 5 (0) | 2021.07.16 |
[백준][2252][C++] 줄 세우기 (0) | 2021.07.15 |
[백준][11438][C++] LCA 2 (0) | 2021.07.14 |
[백준][12015][C++] 가장 긴 증가하는 부분 수열 2 (0) | 2021.07.13 |