[BOJ알고리즘, C++]#6497_전력 난, 최소 신장 트리, 크루스칼

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 최소 신장 트리

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

최소 신장 트리는 간선의 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 이때, 신장 트리는 그래프 내 모든 정점을 순환 구조 없이 최소한의 간선으로 연결하는 부분 그래프를 의미합니다. 대표적인 최소 신장 트리 알고리즘으로 크루스칼 알고리즘, 프림 알고리즘, 솔린 알고리즘이 있습니다.

 

2. 크루스칼 알고리즘

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

크루스칼 알고리즘은 최소 신장 트리 알고리즘 중 하나로 무방향 가중치 그래프에서 간선들을 가중치 기준으로 오름차순 정렬하고, 최소 가중치를 갖는 간선부터 차례대로 Union-Find 연산을 통해 신장 트리를 구성하는 방법입니다. 크루스칼 알고리즘은 간선의 개수가 정점의 개수보다 많을 때 최악의 경우가 되며, O(e long n)의 시간 복잡도를 갖습니다.

 

3. 그래프의 가중치의 합 - 최소 신장 트리의 가중치 합 = 절약 비용!

1. Union-Find 연산 수행을 위해 Union 함수와 Find 함수를 정의합니다.
2. 크루스칼 알고리즘을 구현합니다. 간선 목록을 가중치 기준 오름차순 정렬하고, 최소 가중치를 갖는 간선부터 차례대로 Union-Find 연산을 수행하며 최소 신장 트리를 구성하며, 가중치의 합을 기억합니다.
3. 기존 그래프의 가중치의 합과 최소 신장 트리의 가중치의 합을 빼주어 결과를 출력해 줍니다.

 

---

 

#3. 코드

/*  
    @문제: 어느 한 쌍의 집 사이의 경로에 가로등 불이 켜진 길이 존재하는 동시에, 필요 없는 가로등은 불을 꺼 절약할 수 있는 최대 액수
    @설명
        1. 최소 신장 트리 알고리즘, 크루스칼 활용
        2. 주어진 모든 간선의 가중치의 합을 구해놓고, 최소 신장 트리의 가중치 합과 빼주어 절약 금액 산출
*/

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

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

int m, n;

// Union-Find의 Find연산(path-compression 최적화)
int Find(int x, vector<int>& parent)
{
    if(parent[x] != x)
    {
        return parent[x] = Find(parent[x], parent);
    }
    else return x;
}

// Union-Find의 Union 연산(rank 최적화)
void Union(int rootX, int rootY, vector<int>& parent, vector<int>& rank)
{
    if(rank[rootX] > rank[rootY])
    {
        parent[rootY] = rootX;
    }
    else if(rank[rootY] > rank[rootX])
    {
        parent[rootX] = rootY;
    }
    else
    {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

// 크루스칼, 최소 신장 트리의 가중치의 합 반환
int kruskal(vector<Edge>& edges, int size)
{
    int MST = 0;
    vector<int> parent(size);
    vector<int> rank(size, 0);

    // 부모 목록 초기화
    for(int i=0; i<size; ++i)
        parent[i] = i;

    // 간선 목록을 가중치 기준 오름차순 정렬
    sort(begin(edges), end(edges));

    // 간선 목록 순회, 최소 신장 트리 구성
    for(int i=0; i<edges.size(); ++i)
    {
        int rootX = Find(edges[i].u, parent);
        int rootY = Find(edges[i].v, parent);

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

    return MST;

}

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

    while(1)
    {
        // 집 번호는 0-base 인덱싱
        cin >> m >> n;

        if(m==0 && n ==0) break;

        vector<Edge>edges;
        int originalCost = 0;
        while(n--)
        {
            int x, y, z;
            cin >> x >> y >> z;

            // 절약 금액 계산을 위해 기존의 비용
            originalCost += z;
            // 무방향, 크루스칼 활용
            edges.push_back(Edge({x,y,z}));
        }
        // 기존의 금액 - 절약 후 금액
        cout << originalCost - kruskal(edges, m) << '\n';
    }

    return 0;
}

 

---