[ SWEA 3124 ] 최소 스패닝 트리 (C++)

SWExpertAcademy의 최소 스패닝 트리(3124 / D4) 문제이다.

[ 문제풀이 ]

1) 최소 스패닝 트리(Minimal Spanning Tree)를 구현하는데 사용하는 알고리즘은 대표적으로

   '프림 알고리즘'과 '크루스칼 알고리즘' 이 있다.

   본인은 이 문제를 2가지 방법으로 모두 구현해 보았다.

   문제 자체가, 단순 'MST를 구현해봐라!' 라는 문제이기 때문에, 문제를 풀이하는 설명보다는

   프림알고리즘과 크루스칼 알고리즘에 대한 설명으로 대체하겠다.

   [ 크루스칼 알고리즘에 대해서 알아보기 (Click) ]

   [ 프림 알고리즘에 대해서 알아보기(1) (Click) ]

   [ 프림 알고리즘에 대해서 알아보기(2) (Click) ]

   이 문제를 해결할 때, 프림 알고리즘은 구현방법이 크게 2가지 방법이 있는데, 그 중에서 자료구조 힙을 기반으로 한

   우선순위큐를 사용하는 방법으로 구현하였다.

[ 크루스칼 알고리즘 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 100010
typedef long long ll;
using namespace std;
 
int V, E;
ll Answer;
int Parent[MAX];
vector<pair<int, pair<int, int>>> Edge;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Edge.clear();
    Answer = 0;
}
 
void Input()
{
    cin >> V >> E;
    for (int i = 1; i <= V; i++) Parent[i] = i;
    for (int i = 0; i < E; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Edge.push_back(make_pair(c, make_pair(a, b)));
    }
}
 
int FindParent(int A)
{
    if (A == Parent[A]) return A;
    return Parent[A] = FindParent(Parent[A]);
}
 
bool SameParent(int A, int B)
{
    A = FindParent(A);
    B = FindParent(B);
 
    if (A == B) return true;
    return false;
}
 
void Union(int A, int B)
{
    A = FindParent(A);
    B = FindParent(B);
    int Min_Parent = Min(A, B);
    Parent[A] = Min_Parent;
    Parent[B] = Min_Parent;
}
 
void Solution()
{
    sort(Edge.begin(), Edge.end());
    for (int i = 0; i < E; i++)
    {
        int Dist = Edge[i].first;
        int Node_A = Edge[i].second.first;
        int Node_B = Edge[i].second.second;
 
        if (SameParent(Node_A, Node_B) == false)
        {
            Union(Node_A, Node_B);
            Answer = Answer + Dist;
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ 프림 알고리즘 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
 
#define endl "\n"
#define MAX 100010
typedef long long ll;
using namespace std;
 
int V, E;
vector<pair<int, int>> Node[MAX];
bool Visit[MAX];
ll Answer;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
    memset(Visit, false, sizeof(Visit));
    for (int i = 0; i < MAX; i++) Node[i].clear();
}
 
void Input()
{
    cin >> V >> E;
    for (int i = 0; i < E; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        Node[a].push_back(make_pair(b, c));
        Node[b].push_back(make_pair(a, c));
    }
}
 
void Solution()
{
    priority_queue<pair<int, int>> PQ;
    for (int i = 0; i < Node[1].size(); i++)
    {
        PQ.push(make_pair(-Node[1][i].second, Node[1][i].first));
    }
    Visit[1] = true;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        if (Visit[Cur] == true) continue;
        Visit[Cur] = true;
        Answer = Answer + Cost;
 
        for (int i = 0; i < Node[Cur].size(); i++)
        {
            int nCost = Node[Cur][i].second;
            int Next = Node[Cur][i].first;
 
            if (Visit[Next] == false) PQ.push(make_pair(-nCost, Next));
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}