백준[2887] 행성 터널

아이디어

• MST 알고리즘을 사용할 줄 안다

풀이

1. 각 x,y,z 별로 sort를 해서 바로 양옆 행성과의 거리를 거리가 작은 순으로 priority queue에 저장한다
   -> 왜? : 결국 행성간 거리는 x,y,z간의 거리중 가장 작은 값이다. 각 좌표별로 sort한다면, 바로 옆 행성이 그 좌표에서 가장 작은 거리가 될 것이다.
   2. MST알고리즘을 이용해서(크루스칼 이용) priority_queue가 빌 때 까지 조사한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <string>
#include<queue>
using namespace std;

vector<pair<int,int>> x[3];
priority_queue<pair<int, pair<int, int>>> road;

int n;
int parent[100001];
long long ans = 0;

int find_parent(int x) {
    if (parent[x] == x) return x;

    else return parent[x] = find_parent(parent[x]);
}

void union_parent(int a, int b) {
    int p_a = find_parent(a);
    int p_b = find_parent(b);

    if (p_b < p_a) swap(p_a, p_b);

    parent[p_b] = p_a;
}

bool same_parent(int a, int b) {
    int p_a = find_parent(a);
    int p_b = find_parent(b);

    if (p_a == p_b) return true;
    else return false;
}

void mst() {

    while (!road.empty()) {
        int now_dist = -road.top().first;
        int a = road.top().second.second;
        int b = road.top().second.first;
        road.pop();

        if (!same_parent(a, b)) {
            union_parent(a, b);
            ans += now_dist;
        }
    }
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        int a, b, c; cin >> a >> b >> c;
        x[0].push_back({ a,i });
        x[1].push_back({ b,i });
        x[2].push_back({ c,i });
        parent[i] = i;
    }
    for (int i = 0; i < 3; i++) {
        sort(x[i].begin(), x[i].end());
        for (int pos = 1; pos < x[i].size(); pos++) {
            int dist = abs(x[i][pos].first - x[i][pos - 1].first);
            int left = x[i][pos].second;
            int right = x[i][pos - 1].second;

            road.push({ -dist,{left,right} });
        }
    }

    mst();

    cout << ans;


    return 0;
}

평가

크루스칼 알고리즘 외, 거리를 구하는 방법을 알아야 하는 문제.
간선 거리를 단순 O(n^2)으로 구한다면, 100000*100000 으로 시간복잡도, 공간복잡도가 초과할 수 있습니다.
따라서 행성간 거리는 (min(x,y,z))라는 점을 이용해야 풀 수 있는 문제였습니다.