[백준] 2887번 행성 터널 (C++)

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

 

 

이 문제는 N개의 행성이 주어질때 N-1개의 간선을 사용하여 최소비용으로 N개의 행성을 모두 연결시키는 문제이다.

 

이때 최소 비용의 간선을 계산하는 방법은 min(|xa - xb|, |ya - yb|, |za - zb|)이다.

 

행성을 모두 연결시키는 최소비용을 구하는 문제는 최소 스패닝 알고리즘을 생각해낼 수 있다.

 

구현하는 방법은 대표적으로 2가지로 크루스칼, 프림 알고리즘이 있다.

 

필자는 크루스칼을 더 선호하기에 크루스칼 알고리즘을 사용하여 해결하였다.

 

먼저 x, y, z좌표의 차이중 가장 작은 것의 비용을 사용하기에 한꺼번에 생각하지 말고 x 좌표의 차이, y 좌표의 차이, z좌표의 차이

3개를 따로 넣어주었다. 이때 최소비용을 계산해야한다.

 

비용을 최소로하기 위해서 두 수의 차이가 크지 않아야 한다 이말은 즉 두 수가 비슷하다는 의미이며 대소관계가 크지않다는 이야기이다.

 

정렬을 하여 인접한 두개의 노드의 차이를 계산하여 리스트에 넣어주었다.

 

이후 리스트를 비용에 따라 정렬하여 유니온파인드로 포함하는지 안하는지 확인하여 넣어주었다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int N;
vector<pii> v1;
vector<pii> v2;
vector<pii> v3;
vector<tuple<int, int, int>> edge;
int unf[100001];

int Find(int a) {
    if(a == unf[a]) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a > b) unf[a] = b;
    else unf[b] = a;
}

bool isUnion(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a != b) return false;
    else return true;
}

void solve() {
    int answer = 0;

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());

    for(int i = 0; i < N-1; i++) {
        edge.push_back({abs(v1[i].first - v1[i+1].first), v1[i].second, v1[i+1].second});
        edge.push_back({abs(v2[i].first - v2[i+1].first), v2[i].second, v2[i+1].second});
        edge.push_back({abs(v3[i].first - v3[i+1].first), v3[i].second, v3[i+1].second});
    }

    sort(edge.begin(), edge.end());

    for(int i = 0; i < edge.size(); i++) {
        int cost = get<0>(edge[i]);
        int Node1 = get<1>(edge[i]);
        int Node2 = get<2>(edge[i]);

        if(!isUnion(Node1, Node2)) {
            Union(Node1, Node2);
            answer += cost;
        }
    }

    cout << answer;
}

void Init() {
    for(int i = 1; i <= N; i++) {
        unf[i] = i;
    }
}

void input() {
    cin >> N;

    for(int i = 1; i <= N; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v1.push_back({a, i});
        v2.push_back({b, i});
        v3.push_back({c, i});
    }

    Init();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}