[백준]1197. 최소 스패닝 트리

[문제]

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

[풀이]

 

MST의 가중치를 구하는 문제로 Kruskal 알고리즘을 사용해서 풀었다.

 

정점간의 연결 정보를 입력 받고 벡터에 저장했다.

가중치를 기준으로 벡터를 정렬하고 , 가중치가 작은 것부터 Union-Find를 사용해 묶어줬다.

Union을 하기 전에 Find를 통해 부모가 같은지 미리 확인한다.

( 부모가 같은 상태에서 union을 해버리면 사이클이 발생하므로 )

 

[코드]

시간 : 48ms

 

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

#define MAX 10000

using namespace std;

int parent[MAX]={0,};

int Find(int idx)
{
    if(idx == parent[idx])  return idx;
    else{
        parent[idx] = Find(parent[idx]);
        return parent[idx];
    }
}

void Union(int idx1, int idx2)
{
    idx1 = Find(idx1);
    idx2= Find(idx2);
    if(idx1  != idx2)   parent[idx2] = idx1;
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E;
    cin >> V >> E;
    
    vector <pair<int, pair<int, int>>> v(E);

    for(int i=1;i<=V;i++)   parent[i] = i;
    
    for(int i=0;i<E;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        
        v.push_back(make_pair(c, make_pair(a,b)));
    }
    
    sort(v.begin(),v.end());
    int ans=0;
    
    for(int i=0;i<v.size();i++){
        
        int tmp1 = v[i].second.first;
        int tmp2 = v[i].second.second;
        
        if(Find(tmp1) != Find(tmp2)){
            Union(tmp1,tmp2);
            ans+= v[i].first;
        }
    }
    
    cout << ans;
    
    return 0;
    
}