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

https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

---

문제풀이

보자마자 딱! MST 를 만들면 되겠구나 라고 생각했다. MST를 만드는 알고리즘은 여러가지가 있는데 그중에 kruskal 알고리즘을 사용하기로 했다. 예전에 해본적이 있어서 이걸 사용했다. union-find 알고리즘을 그대로 사용하면된다.

크루스컬 알고리즘의 핵심을 weight별로 정렬하여 cycle이 발생하지 않는 edge를 추가하는 것이다.

union-find 알고리즘으로 cycle 발생 여부를 체크해가며 edge를 추가하면 쉽게 구현할 수 있다.

 

1. 입력받은 edge를 weight 순으로 정렬한다. 이 때 나는 from에 더 작은 번호의 vertex(node)가 들어가게 하였다.

2. 반복을 돌며 union-find 알고리즘을 실행한다. 만약 edge를 넣었을 때 cycle이 생성되면 그 edge는 추가하지 않는다. 생성되지 않으면 정답에 weight를 추가하고, union을 수행한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int parent[1001];

struct edge {
    int w;
    int from;
    int to;
};

bool cmp(edge a, edge b) {
    if(a.w < b.w) return true;
    return false;
}

int findParent(int a) {
    if(parent[a] == a) return a;
    return parent[a] = findParent(parent[a]);
}

void unions(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if(a <= b) parent[b] = a;
    else parent[a] = b;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<edge> v;
    v.reserve(m);
    int answer = 0;

    for(int i=1; i<=n; i++) {
        parent[i] = i;
    }

    for(int i=0; i<m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if(a <= b) v.push_back({c, a, b});
        else v.push_back({c, b, a});
    }

    sort(v.begin(), v.end(), cmp);
    
    for(int i=0; i<m; i++) {
        if(findParent(v[i].from) != findParent(v[i].to)) {
            answer += v[i].w;
            unions(v[i].from, v[i].to);
        }
    }
    cout << answer;
    return 0;
}