[백준OJ] 1922번 네트워크 연결

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

1922번: 네트워크 연결

---

 

-풀이-

모든 지점에서 다른 모든지점까지 연결하는 최소비용의 경로는 최소 스패닝트리 알고리즘을 이용하면 된다.

1) 입력받은 간선들의 정보를 비용기준으로 오름차순 정렬을 해준다.

2) 그런뒤, 작은가격의 간선부터 차례대로 비교를 해주는데, 이어져있는 정점들이 서로 연결되어있지 않다면, 정점을 간선으로 이어준 뒤, 비용을 더해준다.

 

-시간복잡도-

간선을 정렬하는데 드는 비용이 O(MlogM)이 되므로, O(MlogM)이 된다.

 

-코드-

#include <algorithm>
#include<iostream>
using namespace std;

int n,m,result=0;
int parent[1001];
vector<pair<int,pair<int,int>>> edge;

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

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

int main(){
   cin>>n>>m;
    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;
        edge.push_back({c,{a,b}});
    }
    
    sort(edge.begin(),edge.end());
    for(int i=0;i<m;i++){
        int c=edge[i].first;
        int a=edge[i].second.first;
        int b=edge[i].second.second;
        int pa=find(a);
        int pb=find(b);
        if(pa!=pb){
            union_parent(a,b);
            result+=c;
        }
    }
    cout<<result;
}