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

 

 

1922번: 네트워크 연결

 

 

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

using namespace std;

vector<int> p(100001,-1);


int find(int k){
    if(p[k] < 0) return k;
    return p[k] = find(p[k]);
}

bool is_diff_group(int a, int b){
    a = find(a); b = find(b);

    if(a == b) return 0;
    if(p[a] == p[b]) p[a]--;
    if(p[a] < p[b]) p[a] = b;
    else  p[b] = a;

    return 1;

}

int a,b,cost;


tuple<int,int,int> edge[100001];



int n,m;

int main(){
    cin>>n;
    cin>>m;


    for(int i=0; i<m; i++){
        cin>>a>>b>>cost;
        edge[i] = {cost,a,b};
    }

    sort(edge, edge + m);

    int cnt = 0;
    int ans = 0;

    for(int i=0; i<m; i++){
        int a,b,cost;
        tie(cost, a, b) = edge[i];
        if(!is_diff_group(a,b)) continue;
        cnt++;
        ans += cost;
        if(cnt == n-1) break;
    }


    cout<<ans;



}

 

고급 알고리즘 스터디가 있어서 mst를 공부하고 기본 문제를 풀었다.

 

cost가 낮은 것부터 확인을 해야하므로 edge에서 cost를 맨 앞에 놓았다.

정렬 후에 정점을 돌면서 a와 b가 다른 그룹이라면 그 cost만큼 ans에 더해주었다.

 

크루스칼로 구현했는데 프림은 아직 공부를 안해서 잘 모르겠다.