[C++/백준] 1922번: 네트워크 연결

문제 링크

1922번: 네트워크 연결

 

풀이

최소신장트리 문제. 난 union-find 알고리즘으로 풀었다.

1. 간선을 cost 기준으로 오름차순 정렬한다.
2. 각 노드들은 각자의 부분집합으로 자기 자신 값을 넣는다. (subset)
3. 이제 사이클이 생기지 않도록 비용이 적은 간선부터 연결한다. 이 사이클을 확인하는게 union-find이다.
   1. unionFind 함수에서는 a노드와 b노드의 부모 노드를 비교하여 같지 않으면(다른 부분집합이면) 연결한 뒤 true를 return한다.
   2. parent 함수는 노드의 부모 노드를 찾는 함수인데, 재귀 함수를 통해 따라가서 return한다.
   3. merge 함수는 각자 다른 부분집합을 합치는 함수이다. a노드의 부모와 b노드의 부모를 찾아 서로 연결한다. 부모의 숫자가 작은 쪽으로 집합을 합쳤다.
4. 그렇게 unionFind가 true를 return 한다면, 그 간선은 연결되었다는 뜻이므로 answer에 더해준다.

 

코드

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

int parent(int n, vector<int>& subset)
{
    if (n == subset[n]) return n;
    else return parent(subset[n], subset);
}

void merge(int a, int b, vector<int>& subset)
{
    a = parent(a, subset);
    b = parent(b, subset);
    if (a > b) subset[b] = a;
    else subset[a] = b;
}

bool unionFind(int a, int b, vector<int> &subset)
{
    if (parent(a, subset) != parent(b, subset))
    {
        merge(a, b, subset);
        return true;
    }
    else return false;
}

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> v;
    for (int i = 0; i < m; i++)
    {
        int stt, end, cost;
        cin >> stt >> end >> cost;
        v.push_back({ cost, stt, end });
    }

    sort(v.begin(), v.end());

    // 부분집합 만들기
    vector<int> subset(n + 1);
    for (int i = 1; i <= n; i++)
    {
        subset[i] = i;
    }

    int answer = 0;
    for (int i = 0; i < v.size(); i++)
    {
        int stt = v[i][1];
        int end = v[i][2];
        int cost = v[i][0];
        if (unionFind(stt, end, subset))
        {
            answer += cost;
        }
    }

    cout << answer;
}