백준 1922번 - 네트워크 연결

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

그래프와 간선 사이의 가중치가 주어졌을 때

모든 노드가 연결이 되어 있으면서 최소 비용으로 연결되는 경우를 구하면 된다.

즉, 최소신장트리 문제로 그리디한 방법으로 풀 수 있다.

대표적으로 크루스칼과 프림 알고리즘이 있는데

크루스칼 방식으로 풀어보았다.

컴퓨터가 연결되어 있는 비용을 오름차순으로 먼저 정렬한다.

다음으로 각각의 컴퓨터를 합쳐주면 되는데

이때 parent 변수를 이용해 연결되어 있는지 확인하면 된다.

처음에 parent변수에는 i번째 컴퓨터에 i값이 들어있다.

만약에 둘을 합쳐줄 때 parent값이 다르면 합친 다음에 parent값을 동일하게 한다.

parent값이 같다는 것은 서로가 연결되어 있다는 의미이기 때문이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct str{
    int s,e,w;
    str(int s,int e,int w):s(s),e(e),w(w){};
};
 
bool operator<(str s1,str s2){
    return s1.w<s2.w;
}
 
int parent[1001]={0};
int find(int k){
    while(parent[k]!=k){
        k=parent[k];
    }
    return k;
}
int main(){
    
    int N,M;
    cin>>N>>M;
    
    int s,e,w;
    vector<str> vec;
    for(int i=0;i<M;i++){
        scanf("%d %d %d",&s,&e,&w);
        vec.push_back(str(s,e,w));
    }
    
    int ans=0;
    int p1,p2=0;
    sort(vec.begin(),vec.end());
    
    for(int i=1;i<=N;i++)
        parent[i]=i;
    
    for(int i=0;i<vec.size();i++){
        
        p1=find(vec[i].s);
        p2=find(vec[i].e);
        
        if(p1==p2)
            continue;
        
        if(p1<p2)   parent[p1]=p2;
        else    parent[p2]=p1;
        ans+=vec[i].w;
    }
    
    cout<<ans<<endl;
    return 0;
}