[백준 알고리즘] 1197번 최소 스패닝 트리 문제풀이 c++

 

최소 스패닝 트리 문제를 크루스칼 알고리즘을 적용하여 풀었다.

find_root는 연결된 최상위 노드를 찾는 함수이다.

union_root는 연결할 2개의 노드가 최상위노드가 다르면 같게 바꿔주는 함수이다.

간선과 가중치에 대한 정보를 edge vector에 저장하고 가중치 기준으로 sort한 후,

edge벡터를 탐색함으로 가중치가 최소인 최소스패닝트리를 구할 수 있다.(그리디 알고리즘)

 

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

using namespace std;

vector<pair<int, pair<int, int>>> edge;
vector<int> parent;

int find_root(int x){
	if(parent[x] == x)
		return x;
	else
		return parent[x] = find_root(parent[x]);
}

void union_root(int x, int y){
	x = find_root(x);
	y = find_root(y);

	if(x != y){
		parent[y] = x;
	}
}



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

	for(int i=0; i<n; i++){
		parent.push_back(i);
	}

	int a, b, c;
	for(int i=0; i<m; i++){
		cin >> a >> b >> c;
		edge.push_back(make_pair(c, make_pair(a-1,b-1)));
	}

	sort(edge.begin(), edge.end());
	
	long long answer = 0;
	int	count = 0;
	for(int i=0; i < edge.size(); i++){
		int x = edge[i].second.first;
		int y = edge[i].second.second;
		int w = edge[i].first;
		


		if(find_root(x) != find_root(y)){
			answer += w;
			union_root(x,y);
			count ++;
		}

		if(count == n-1){
			break;
		}
	}
	cout << answer;

	return 0;
}