[ 백준 1922 ] 네트워크 연결 (C++)

백준의 네트워크연결(1922) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 본 문제는 MST를 구현해야 하는 문제이다. 우리가 사용할 수 있는 대표적인 알고리즘으로는 크루스칼 알고리즘이 있다.

   아직 크루스칼 알고리즘에 대해서 잘 모른다면 아래 링크를 타고 글을 읽고 오길 바란다 ! 문제가 훨씬 쉬워질 것이다.

   [ 크루스칼 알고리즘 개념부터 구현까지 알아보기 ]

2) 사실 크루스칼 알고리즘을 이해했다면, 이 문제를 왜 크루스칼 알고리즘으로 풀어야 하는지, 어떻게 풀어야 하는지

   모두 이해할 수 있을 거라 생각한다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N, M, Answer;
int Parent[MAX];
vector<pair<int, pair<int, int>>> Edge;
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        Edge.push_back(make_pair(c, make_pair(a, b)));
    }
}
 
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()
{
    sort(Edge.begin(), Edge.end());
    for (int i = 1; i <= N; i++)
    {
        Parent[i] = i;        // 초기값 설정
    }
    
    for (int i = 0; i < M; i++)
    {
        if (SameParent(Edge[i].second.first, Edge[i].second.second) == false)
        {
            Union(Edge[i].second.first, Edge[i].second.second);
            Answer = Answer + Edge[i].first;
        }
    }
 
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}