[ 백준 1197 ] 최소 스패닝 트리 (C++)

백준의 최소스패닝트리(1197) 문제이다.

[ 문제 바로가기 ]

[ 문제 풀이]

1) 이 문제는 Minimal Spanning Tree를 구현해야 하는 문제이다. 크루스칼 알고리즘을 이용하면 쉽게 구할 수 있다.

   아직 크루스칼 알고리즘에 대해서 잘 모른다면 아래의 링크를 타고 글을 읽고 오도록 하자.

   [ 크루스칼 알고리즘의 개념 및 구현방법 알아보기(Click) ]

  사실, 위의글을 읽고 왔다면 이 문제에 대한 풀이를 보고 온 것과 마찬가지이다. 다른거 하나 없이, 그대로 구현하면 되기 때문

  이다.

  위의 글을 읽었다면, 이 문제를 다시 한번 읽어보고 혼자서 구현해보기 바란다 !

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 10000 + 1
using namespace std;
 
int Vertex, E, Answer;
int Parent[MAX];
vector<pair<int, pair<int, int>>> V;
 
void Input()
{
    cin >> Vertex >> E;
    for(int i = 0; i < E; i++)
    {
        int From, To, Cost;
        cin >> From >> To >> Cost;
 
        V.push_back(make_pair(Cost, make_pair(From, To)));
    }
 
    sort(V.begin(), V.end());
}
 
int Find(int x)
{
    if (Parent[x] == x) return x;
    else return Parent[x] = Find(Parent[x]);
}
 
void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x != y) Parent[y] = x;
}
 
bool SameParent(int x, int y)
{
    x = Find(x);
    y = Find(y);
 
    if (x == y) return true;
    else return false;
}
 
void Solution()
{
    for (int i = 1; i <= Vertex; i++)
    {
        Parent[i] = i;
    }
 
    for (int i = 0; i < E; i++)
    {
        if (SameParent(V[i].second.first, V[i].second.second) == false)
        {
            Union(V[i].second.first, V[i].second.second);
            Answer = Answer + V[i].first;
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}