[백준/Baekjoon] 2887 행성 터널 C++ :: MST

728x90

728x90

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

---

1. Logic

크루스칼 알고리즘을 활용해서 풀이했다. 이 문제를 풀 때 핵심은 두 행성을 연결할 떄 드능 비용이 min(|x1-x2|, |y1-y2|, |z1-z2|)라는 지문에서 찾을 수 있다. x, y, z의 좌표차가 가장 작은 값이 두 사이의 거리라는 뜻이다. 그러므로 각 x, y, z좌표를 받은 후 정렬을 하게 되면 배열의 앞뒤에 있는 좌표가 가장 차이가 적은 값 순서대로 정렬이 될 것이다. 이 좌표들을 바탕으로 앞뒤 행성의 거리를 구해서 저장하고 다시 오름차순 정렬하여 0번째 인덱스부터 크루스칼을 통해 최단 거리를 구하면 최소 비용을 구할 수 있다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int parent[100001];
int n;
vector<pair<int, int>> cordinate[3];
vector<pair<int, pair<int, int>>> dist;

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

bool isUnion(int x, int y) {
    x = find(x);
    y = find(y);
    
    if(x == y) return true;
    else return false;
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    
    if(x == y) return;
    
    if(x > y) parent[x] = y;
    else parent[y] = x;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int x, y, z;
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> x >> y >> z;
        
        cordinate[0].push_back({x, i});
        cordinate[1].push_back({y, i});
        cordinate[2].push_back({z, i});
        parent[i] = i;
    }
    
    sort(cordinate[0].begin(), cordinate[0].end());
    sort(cordinate[1].begin(), cordinate[1].end());
    sort(cordinate[2].begin(), cordinate[2].end());
    
    for(int i = 0; i < n-1; i++) {
        dist.push_back({abs(cordinate[0][i].first - cordinate[0][i+1].first), {cordinate[0][i].second, cordinate[0][i+1].second}});
        dist.push_back({abs(cordinate[1][i].first - cordinate[1][i+1].first), {cordinate[1][i].second, cordinate[1][i+1].second}});
        dist.push_back({abs(cordinate[2][i].first - cordinate[2][i+1].first), {cordinate[2][i].second, cordinate[2][i+1].second}});
    }
    
    sort(dist.begin(), dist.end());
    
    int ans = 0;
    
    for(int i = 0; i < dist.size(); i++) {
        if(!isUnion(dist[i].second.first, dist[i].second.second)) {
            ans += dist[i].first;
            merge(dist[i].second.first, dist[i].second.second);
        }
    }
    
    cout << ans;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90