1922번 네트워크 연결[C++]

1. 개요

 안녕하세요. 이번에 풀어본 문제는 가중치가 있는 무방향 그래프에서 간선들의 가중치 합이 최소가 되는 트리인 최소 신장 트리(MST)를 추출하는 알고리즘인 Kruskal 또는 Prim 알고리즘을 사용하는 유형의 문제였습니다. 어떤 응용 없이 알고리즘을 사용하기만 하면 풀 수 있는 문제라 최소 신장 트리를 처음 접해보시는 분들이 연습용으로 적합하다는 생각을 했습니다. Kruskal은 disjoint-set을 구현하는 Union-Find을 사용하여 풀이할 수 있고, Prim은 우선순위큐를 사용하여 풀이할 수 있습니다. Kruskal 알고리즘을 개인적으로 선호하고 구현 난이도도 더 쉽다고 생각합니다. 

 

2. 문제 풀이

 Kruskal 알고리즘을 사용해서 최소 신장 트리를 추출하여 풀이했습니다. 모든 간선 정보를 tuple<int, int, int> 자료형을 사용하여 저장하고 가중치에 대해서 오름차순으로 정렬하여 순회합니다. 각 간선에 저장되어 있는 정점 u, v를 union-find 기법을 사용해 union하고 성공했을 시 가중치의 합을 더해주었습니다. 트리는 N개의 정점이 N - 1개의 간선으로 이루어진 그래프이므로 union 성공 횟수가 N - 1이 되었을 때 순회를 종료하였고 그때까지 더한 가중치의 합을 출력하였습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int INF = 0x7fffffff;

int n, m;
vti edges;
vi p;

int find(int x) {
    return (p[x] < 0 ? x : p[x] = find(p[x]));
}

bool merge(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) {
        return 0;
    }

    if(p[x] > p[y]) {
        swap(x, y);
    }
    
    p[x]--;
    p[y] = x;

    return 1;
}

int main() {
    fastio(nullptr, false);

    cin >> n >> m;

    vti(m).swap(edges);
    vi(n+1, -1).swap(p);

    for(auto &[w, u, v] : edges) {
        cin >> u >> v >> w;
    }

    sort(all(edges));

    int ans{}, cnt{};
    for(auto &[w, u, v] : edges) {
        if(cnt == n - 1) {
            break;
        }

        if(merge(u, v)) {
            ans += w;
            cnt++;
        }
    }

    cout << ans;
}

 

4. 제출 결과