백준 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;
}