백준 1922번 - 네트워크 연결

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

1922번: 네트워크 연결

 

• 필요한 배경지식

최소 신장 트리(Minimum Spanning Tree) : 크루스칼(Kruskal) 알고리즘

 

 

 

• 문제 해결 방법

단순 MST문제입니다.

유니온 파인드를 활용한 크루스칼 알고리즘을 이용했습니다.

 

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;
using tpi = tuple<int,int,int>;

int N,M;
vector<tpi> edge;
int par[1001]{};


int find(int k){
    if(k == par[k]) return k;
    else return par[k] = find(par[k]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    par[a] = b;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    for(int i=0; i<=N; i++) par[i] = i;
    cin>>M;
    int a,b,c;
    for(int i=0; i<M; i++){
        cin>>a>>b>>c;
        edge.push_back({c,a,b});
    }
    sort(edge.begin(), edge.end());

    int ans = 0;
    for(auto e : edge){
        int a,b,c;
        tie(a,b,c) = e;
        if(find(b) == find(c)) continue;
        merge(b,c);
        ans += a;
    }

    cout<<ans;
}