최소신장트리(MST) 구현 - [크루스칼 알고리즘]

최소비용으로 모든 정점이 연결되는 간선을 찾는 법.

 

1. 간선을 오름차순으로 정렬한다.

2. 비용이 가장 적은 순으로 간선을 추가한다.

3. 추가 하되 사이클이 형성 안되도록 한다.

 

목표: 최소비용, 간선

 

6497번: 전력난 (acmicpc.net)

6497번: 전력난

 

풀이 시도

 

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

using namespace std;

// 부모 노드를 찾는 함수
int getParent(const vector<int>& parent, int node)
{
    if (parent[node] == -1)
        return node;
    else
        return getParent(parent, parent[node]);
}

// 크루스칼 알고리즘 구현
int Main() {
    vector<vector<int>> question;       //문제
    vector<int> line = { 0,1,7 };
    question.emplace_back(line);
    line = { 0,3,5 };
    question.emplace_back(line);
    line = { 1, 2, 8 };
    question.emplace_back(line);
    line = { 1, 3, 9 };
    question.emplace_back(line);
    line = { 1, 4, 7 };
    question.emplace_back(line);
    line = { 2, 4, 5 };
    question.emplace_back(line);
    line = { 3, 4, 15 };
    question.emplace_back(line);
    line = { 3, 5, 6 };
    question.emplace_back(line);
    line = { 4, 5, 8 };
    question.emplace_back(line);
    line = { 4, 6, 9 };
    question.emplace_back(line);
    line = { 5, 6, 11 };
    question.emplace_back(line);

    //풀이//
    vector<int> parent(7, -1);		//-1이면 부모가 자기 자신이라는 뜻

    sort(question.begin(), question.end(), compare2);

    int max_cost = 0;
    int min_cost = 0;
    vector<vector<int>> result; 	//연결된 간선 저장용

    for (auto current : question)
    {
        max_cost += current[2];
        int src_parent = getParent(parent, current[0]);
        int dst_parent = getParent(parent, current[1]);

        if (src_parent != dst_parent)	//서로 부모가 다르면 연결
        {
            min_cost += current[2];
            parent[src_parent] = dst_parent;	//두 노드의 부모를 동기화
            result.push_back(current);
        }
    }

    cout << "최소 비용 : " << min_cost << endl;
    cout << "절약 비용 : " << max_cost - min_cost << endl;
    cout << "연결 간선 : " << endl;;
    for (int i = 0; i < result.size(); ++i)
    {
        cout << "[" << result[i][0] << ", " << result[i][1] << ", " << result[i][2] << "]" << endl;
    }
}