(C++) - 백준(BOJ) 1922번 : 네트워크 연결 답

 

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

1922번: 네트워크 연결

전체 네트워크 연결비용을 출력하는 문제이므로 크루스칼로 풀었습니다.

 

풀이방법

 1. 간선을 입력받습니다.

 

 2. 간선을 비용 오름차순으로 정렬합니다.

 

 3. 두 정점의 parent가 다르다면 다른 집합이므로 적은 비용의 간선을 추가하고 union(merge)를 해줍니다.

 

 4. 정답(MST 비용)을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int parent[1001];

struct Edge { int u, v, w; };

vector <Edge> graph;

bool cmp(Edge a, Edge b){
    return a.w < b.w;
}

int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int a, int b){
    if(find(a) != find(b)){
        parent[a] = b;
    }
}

int main(){
    cin >> n >> m;
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        graph.push_back({u,v,w});
    }
    sort(graph.begin(),graph.end(),cmp);
    for(int i = 1; i <= n; i++) parent[i] = i;
    for(int i = 0; i < graph.size(); i++){
        int aParent = find(graph[i].u);
        int bParent = find(graph[i].v);
        if(aParent != bParent){
            merge(aParent,bParent);
            ans += graph[i].w;
        }
    }
    cout << ans << '\n';
}