[BOJ알고리즘, C++]#2887_행성 터널, 최소 신장 트리(MST), 크루스칼

 

#1. 문제

2887번: 행성 터널

 

---

 

#2. 풀이

 

1. 크루스칼 알고리즘

 

[자료구조]#6_그래프

크루스칼 알고리즘은 간선 중심의 최소 신장 알고리즘입니다. 크루스칼 알고리즘은 그래프의 간선들을 가중치 기준 오름차순 정렬하여, 가중치가 가장 작은 간부터 차례대로 Union-Find 연산을 통해 두 정점의 서로소 여부 확인(Find) 및 하나의 집합으로 합치는 작업(Union)을 수행하고 최소 신장 트리를 구성하는 간선으로 선택합니다. 크루스칼 알고리즘의 동작 방식은 간선 목록의 가중치 기준 오름차순 정렬, 간선 목록 순회 및 Union-Find 연산, 최소 신장 트리 구성으로 설명할 수 있겠습니다.

 

2. x, y, 그리고 z 값 기준 오름차순 정렬 및 간선 구성 그 후 크루스칼 진행!

 

1. 먼저, x, y, 그리고 z 값을 기준으로 '3'번의 정렬 및 간선 구하기 작업을 진행합니다. 쉽게 말해, 각 행성에 대하여 3번의 오름차순 정렬 및 기준값(x, y, z 중 하나)을 통해 계산한 가중치를 갖는 간선을 얻습니다.
2. 이렇게 구한 간선 목록으로 크루스칼 알고리즘을 수행하고, 최소 신장 트리의 간선 수가 N-1개가 되면, 크루스칼 알고리즘을 종료하고 정답을 출력합니다. 다소 그리디 한 느낌이 있지만, 이게 정답이랍니다.. 허허

 

---

 

#3. 코드

 

// #1. 실패 코드, Prim 알고리즘 활용

// #include <iostream>
// #include <vector>
// #include <queue>
// #include <cmath> // 거리 계산을 위한 헤더 파일 추가
// using namespace std;

// struct Star
// {
//     int idx;
//     double x, y, z;
// };

// struct Edge
// {
//     Star from, to;
//     double weight;

//     // 비교 연산자 수정
//     bool operator<(const Edge &other) const
//     {
//         return weight < other.weight;
//     }
// };

// int N;
// vector<Star> stars;

// // 유클리드 거리를 계산하는 함수
// double calculateDistance(const Star &a, const Star &b)
// {
//     return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + pow(a.z - b.z, 2));
// }

// int Prim()
// {
//     priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
//     vector<bool> visited(N, false);
//     int MSTSum = 0;

//     // 정점 0을 시작 정점으로 선택
//     visited[0] = true;

//     // 시작 정점과 나머지 모든 정점 간의 간선을 우선순위 큐에 삽입
//     for (int i = 1; i < (int)stars.size(); ++i)
//     {
//         double dist = calculateDistance(stars[0], stars[i]); // 유클리드 거리 계산 사용
//         pq.push(Edge({stars[0], stars[i], dist}));
//     }

//     while (!pq.empty())
//     {
//         Edge curEdge = pq.top();
//         pq.pop();

//         Star to = curEdge.to;
//         double weight = curEdge.weight;

//         if (visited[to.idx])
//             continue;

//         MSTSum += weight;
//         visited[to.idx] = true;

//         // 현재 정점과 연결된 간선을 우선순위 큐에 삽입
//         for (int i = 0; i < N; ++i)
//         {
//             if (!visited[i] && i != to.idx)
//             {
//                 double dist = calculateDistance(to, stars[i]); // 유클리드 거리 계산 사용
//                 pq.push(Edge({to, stars[i], dist}));
//             }
//         }
//     }

//     return MSTSum;
// }

// int main()
// {
//     ios_base::sync_with_stdio(false);
//     cin.tie(0);
//     cout.tie(0);

//     cin >> N;

//     for (int i = 0; i < N; ++i)
//     {
//         double x, y, z;
//         cin >> x >> y >> z;

//         stars.push_back(Star({i, x, y, z}));
//     }

//     // 프림 알고리즘 수행
//     cout << Prim();

//     return 0;
// }

// #2. 성공 코드 :  모든 간선을 우선 구하고, 크루스칼 수행

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Star
{
    int idx, x, y, z;
};

struct Edge
{
    int from, to, weight;
    bool operator<(const Edge &other) const
    {
        return weight < other.weight;
    }
};

int N;
vector<Star> star;
vector<Edge> edge;
vector<int> parent;

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

bool merge(int u, int v)
{
    u = find(u);
    v = find(v);
    if (u == v)
        return false;
    parent[u] = v;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    star.resize(N);
    parent.resize(N);
    for (int i = 0; i < N; i++)
    {
        star[i].idx = i;
        cin >> star[i].x >> star[i].y >> star[i].z;
    }

    for (int d = 0; d < 3; d++)
    {
        sort(star.begin(), star.end(), [d](Star &a, Star &b)
             {
            if(d == 0) return a.x < b.x;
            else if(d == 1) return a.y < b.y;
            else return a.z < b.z; });
        for (int i = 0; i < N - 1; i++)
        {
            int w;
            if (d == 0)
                w = abs(star[i].x - star[i + 1].x);
            else if (d == 1)
                w = abs(star[i].y - star[i + 1].y);
            else
                w = abs(star[i].z - star[i + 1].z);
            edge.push_back({star[i].idx, star[i + 1].idx, w});
        }
    }

    sort(edge.begin(), edge.end());
    for (int i = 0; i < N; i++)
        parent[i] = i;

    int answer = 0, cnt = 0;
    for (auto &e : edge)
    {
        if (merge(e.from, e.to))
        {
            answer += e.weight;
            if (++cnt == N - 1)
                break;
        }
    }

    cout << answer;

    return 0;
}

 

---