백준 2887 행성터널 - C++

문제 링크 : https://www.acmicpc.net/problem/2887

문제 설명

이번 문제는 크루스칼 알고리즘을 사용하여 풀었다.
이 문제는 노드들 끼리의 가중치가 주어지지 않기 때문에, 직접 구해야하는데 일일이 비교(n^2)했다가는 시간초과를 피하지 못 할거 같았다. 그래서 나는 처음 프림 알고리즘을 사용하려했으나, 시간 초과를 피할 방법이 떠오르지 않아 크루스칼 알고리즘을 사용하여 미리 풀어봤다.
크루스칼 알고리즘은 모든 간선을 가중치 기준으로 오름차순으로 정렬하고, 이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하는 것이다.
이 문제의 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|) 으로 3차원상의 거리를 쟤는것이 아닌, 2차원상의 거리를 계산하는것, 그리하여 행성들의 좌표들을 x, y, z 각각 모두 오름차순으로 연결 하고, Union-find를 이용하여 정렬된 행성들을 연결 시켜주면 되는것이다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector <pair<int,int > > xyz[3];                  //  행성 좌표 담는 변수 / (x or y or z , 몇번째인지)
vector <pair<int,pair<int,int> > > planet;        // 정렬하여 거리가 적은 행성 담는 함수 (거리, n번째와 n+1번째)
int n;
int parent[100001];
int result;
int findparent(int x)       // 연결된 부모 찾는 함수 
{
    if (parent[x] == x) return x;
    return parent[x] = findparent(parent[x]);
}
void unionparent(int x, int y)  // 묶어 주는 함수
{
    x = findparent(x);
    y = findparent(y);
    if (x < y)
        parent[y] = x;
    else if (x > y)
        parent[x] = y;
}
int sameparent(int x, int y)    // 부모가 같은지 확인하는 함수 
{
    x = findparent(x);
    y = findparent(y);
    if (x == y)
        return true;
    else
        return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)             // 벡터에 x, y , z  각각 위치와 몇번째 인지 담아주기
    {
        int x, y , z;
        cin >> x >> y >> z;
        xyz[0].push_back(make_pair(x,i));
        xyz[1].push_back(make_pair(y,i));
        xyz[2].push_back(make_pair(z,i));
        parent[i] = i;
    }
    for (int i = 0; i < 3; i++)           // 정렬되면 거리가 오름차순으로 비슷한거끼리 나열된다.
        sort(xyz[i].begin(),xyz[i].end());
    for (int i = 0; i < n-1; i++)        // 최종적으로 planet 벡터에 정렬된 xyz 벡터의 n번째와 n+1번째 거리와 몇번째인지 각각 넣어주기
    {
        planet.push_back(make_pair(abs(xyz[0][i].first - xyz[0][i+1].first),make_pair(xyz[0][i].second,xyz[0][i+1].second)));
        planet.push_back(make_pair(abs(xyz[1][i].first - xyz[1][i+1].first),make_pair(xyz[1][i].second,xyz[1][i+1].second)));
        planet.push_back(make_pair(abs(xyz[2][i].first - xyz[2][i+1].first),make_pair(xyz[2][i].second,xyz[2][i+1].second)));
    }
    sort(planet.begin(),planet.end());  // 정렬
    for (int i = 0; i < planet.size(); i++)
    {
        if (!sameparent(planet[i].second.first,planet[i].second.second))   // 부모가 같지 않으면 연결되지 않은것, 연결해주기
        {
            result += planet[i].first;
            unionparent(planet[i].second.first,planet[i].second.second);
        }
    }
    cout << result;
    return 0;
}