[백준/C++] 2887번. 행성 터널
[백준/C++] 1516번. 게임 개발
1. 문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)
이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
3. 출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
4. 풀이
최소 신장 트리
문제- 행성의 정보를 입력 받는다.
- 터널로 연결할 때 드는 비용은
min(|xA-xB|, |yA-yB|, |zA-zB|)
이기 때문에 x, y, z를 각각 배열로 만들어 준다. - 각 배열을 정렬하고 비용을 구해서
x[i+1].first - x[i].first
edges
배열에 삽입한다. edges
배열을 정렬하고 사이클이 있는지 확인하면서 최단 거리를 구한다.
5. 처음 코드와 달라진 점
- x, y, z를 따로 해주지 않고 모든 경우의 수를 구해서 메모리 초과가 났다.
6. 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int parent[1000001];
vector<pair<int, pair<int, int> > > edges;
int findParent(int x) {
if(parent[x] == x) return x;
else return findParent(parent[x]);
}
void unionParent(int a, int b) {
a = findParent(a);
b = findParent(b);
if(a < b) parent[b] = a;
else parent[a] = b;
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>n;
for (int i = 0; i < n; i++) {
parent[i] = i;
}
vector<pair<int, int> > x;
vector<pair<int, int> > y;
vector<pair<int, int> > z;
for (int i = 0; i < n; i++) {
int a, b, c;
cin>>a>>b>>c;
x.push_back(make_pair(a, i));
y.push_back(make_pair(b, i));
z.push_back(make_pair(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++) {
edges.push_back(make_pair(x[i+1].first - x[i].first, make_pair(x[i].second, x[i+1].second)));
edges.push_back(make_pair(y[i+1].first - y[i].first, make_pair(y[i].second, y[i+1].second)));
edges.push_back(make_pair(z[i+1].first - z[i].first, make_pair(z[i].second, z[i+1].second)));
}
sort(edges.begin(), edges.end());
int answer = 0;
for (int i = 0; i < edges.size(); i++) {
int a, b, cost;
cost = edges[i].first;
a = edges[i].second.first;
b = edges[i].second.second;
if(findParent(a) != findParent(b)) {
answer += cost;
unionParent(a, b);
}
}
cout<<answer;
}
Author And Source
이 문제에 관하여([백준/C++] 2887번. 행성 터널), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/BOJ2887저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)