[BOJ알고리즘, C++]#16398_행성 연결, 최소 신장 트리, 크루스칼, Kruskal

 

#1. 문제

16398번: 행성 연결

 

---

 

#2. 풀이

 

1. 최소 신장  트리

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

최소 신장 트리는 가중치 그래프에서 간선들이 갖는 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 대표적인 최소 신장 트리 알고리즘은 Kruskal 알고리즘(간선 중심+우선순위 큐), Prim 알고리즘(정점 중심), 그리고 Sollyn 알고리즘(집합 중심)이 있습니다. 

 

2. 크루스칼 알고리즘

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

크루스칼 알고리즘은 간선 중심의 최소 신장 트리 알고리즘입니다. 크루스칼 알고리즘은 무방향 가중치 그래프에서 간선들을 가중치 기준 오름차순 정렬하여 가장 작은 가중치를 갖는 간선부터 차례대로 Union-Find 연산을 통해 최소 신장 트리를 구성합니다. 크루스칼 알고리즘은 간선의 개수가 E일 때, O(E log E)의 시간 복잡도를 갖습니다. 

 

3. 크루스칼은 오름차순 정렬 + Union-Find 연산!

1. 먼저, Union-Find 연산을 위해 Find() 함수와 Union()함수를 정의합니다.
2. 간선 목록을 구성하고, Kruskal을 수행합니다.

 

---

 

#3. 코드

 

/*
    [문제] : 각 행성을 모두 연결하는 최소 신장 트리 비용
    [설명]
            1. 크루스칼 알고리즘 활용
            2. 크루스칼 알고리즘은 간선 중심의 알고리즘으로, 간선 목록 만들기 + Union-Find 연산 구현
*/

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

#define MAX 1001

struct Edge
{
    int u, v, w;
    const bool operator<(const Edge& Other)
    {
        return w < Other.w;
    }
};

int N;
long long MST;
int parent[MAX];
vector<Edge> edges;

int Find(int x)
{
    if(parent[x] != x)
    {
        parent[x] = Find(parent[x]);
    }

    return parent[x];
}

void Union(int rootX, int rootY)
{
    parent[rootX] = rootY;
}

void Kruskal()
{
    // #1. 부모 노드를 자기 자신으로 초기화
    for(int i=0; i<=N; ++i)
        parent[i] = i;

    // #2. 간선 목록을 오름차순 정렬
    sort(begin(edges), end(edges));

    // #3. 간선 목록 순회하며, MST 구성
    for(int i=0; i<(int)edges.size(); ++i)
    {
        int rootX = Find(edges[i].u);
        int rootY = Find(edges[i].v);

        if(rootX != rootY)
        {
            MST += edges[i].w;
            Union(rootX, rootY);
        }
    }

    cout << MST;
}

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

    cin >> N;

    // #1. 간선 목록 초기화
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<N; ++j)
        {
            int cost;
            cin >> cost;

            if(i != j)
            {
                edges.push_back(Edge({i,j,cost}));
            }
        }
    }

    // #1. 크루스칼 알고리즘
    Kruskal();

    return 0;
}

 

---