행성 터널 (feat. 백준, 2887번)

행성 터널
https://www.acmicpc.net/problem/2887

2887번: 행성 터널

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
struct Star{
    int number;
    int x;
    int y;
    int z;
};
int N;
vector<Star> stars, stars_x, stars_y, stars_z;
bool visit[100001];
vector<pair<int, int>> arr[100001];     // 다음 위치, 거리
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;      // 거리, 다음 위치
int distance(const Star& v1, const Star& v2){
    return min(min(abs(v1.x - v2.x), abs(v1.y - v2.y)), abs(v1.z - v2.z));
}
bool sort_x(const Star& v1, const Star& v2){
    return v1.x < v2.x;
}
bool sort_y(const Star& v1, const Star& v2){
    return v1.y < v2.y;
}
bool sort_z(const Star& v1, const Star& v2){
    return v1.z < v2.z;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int dist, ans = 0;
    cin >> N;
    for(register int n = 1, x, y, z; n <= N; ++n)
        cin >> x >> y >> z, stars.push_back(Star{n, x, y, z}), visit[n] = false;
    stars_x = stars, stars_y = stars, stars_z = stars;
    sort(stars_x.begin(), stars_x.end(), sort_x);
    sort(stars_y.begin(), stars_y.end(), sort_y);
    sort(stars_z.begin(), stars_z.end(), sort_z);
    for(register int i = 1; i < N; ++i){
        dist = distance(stars_x[i - 1], stars_x[i]);
        arr[stars_x[i - 1].number].push_back(make_pair(stars_x[i].number, dist));
        arr[stars_x[i].number].push_back(make_pair(stars_x[i - 1].number, dist));

        dist = distance(stars_y[i - 1], stars_y[i]);
        arr[stars_y[i - 1].number].push_back(make_pair(stars_y[i].number, dist));
        arr[stars_y[i].number].push_back(make_pair(stars_y[i - 1].number, dist));

        dist = distance(stars_z[i - 1], stars_z[i]);
        arr[stars_z[i - 1].number].push_back(make_pair(stars_z[i].number, dist));
        arr[stars_z[i].number].push_back(make_pair(stars_z[i - 1].number, dist));
    }
    q.push(make_pair(0, 1));
    register int next, nnext, cnt = 0;
    while(!q.empty()){
        if(cnt == N)
            break;
        dist = q.top().first, next = q.top().second; q.pop();
        if(visit[next])
            continue;
        visit[next] = true;
        ans += dist;
        ++cnt;
        for(auto& v : arr[next]){
            nnext = v.first, dist = v.second;
            q.push(make_pair(dist, nnext));
        }
    }
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 생성하는 문제입니다.

두 행성간 모든 거리를 구하게 되면 100000 * 100000 의 총 배열이 생성되므로 메모리초과가 발생합니다.

따라서 x, y, z 각각의 위치에 대해서 정렬하고, 앞선 정렬의 행성으로 우선순위를 정해줍니다.