[백준 알고리즘] 1197번 - 최소 스패닝 트리 (크루스칼 알고리즘)

1. 문제 및 예시 실행 결과

 

 solved.ac의 CLASS가 올라갈수록 모르는 알고리즘이 많다. 어제 토스 코테 한번 찍먹하고 많이 반성하게 됐다. 모르는 것을 공부하는게 맞는 것 같다. Union-find를 활용한  크루스칼 알고리즘을 공부하고 적용해보았다. 한큐에 초록 글자가 떠서 너무 좋았다.

 

출처: https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

---

---

2. 풀이과정

 

 문제를 잘게 나눠봤다.

 

1. 문제 나누기
2. 입력
3. root가 같으면 continue
4. 아니면 정답에 더하고 두 노드 union 처리

 

 다음은 정답 코드이다.

 

#include <iostream>
#include <vector>
#include <queue>

/*
* 문제 나누기
* 입력
* 찾기
* root 확인
* 아니면 찾기
*/

using namespace std;

priority_queue<pair<int, pair<int, int>>> edges;
int roots[10001];

int get_root(int node) {
	if (roots[node] == node) {
		return node;
	}
	else
		return roots[node] = get_root(roots[node]);
}

bool find(int node1, int node2) {

	int root1 = get_root(node1);
	int root2 = get_root(node2);

	if (root1 == root2)
		return true;
	else
		return false;
}

void union_node(int node1, int node2) {
	int root1 = get_root(node1);
	int root2 = get_root(node2);

	if (root1 > root2)
		roots[root1] = root2;
	else
		roots[root2] = root1;
}


int main(void) {
	int V, E;
	int count_node = 1;
	int ans = 0;

	cin >> V >> E;


	for (int i = 0; i <= V; i++) {
		roots[i] = i;
	}

	for (int i = 0; i < E; i++) {
		int A, B, C;
		cin >> A >> B >> C;

		edges.push(make_pair(-C, make_pair(A, B)));
	}

	if (V == 1) {
		cout << 0;
		return 0;
	}
	
	while (count_node < V) {


		//cout << count_node << endl;

		int weight = -edges.top().first;
		int node1 = edges.top().second.first;
		int node2 = edges.top().second.second;


		edges.pop();

		//만약 두 노드가 연결되어있으면 그냥 진행

		if (find(node1, node2)) {
			continue;
		}

		//아니면 ans추가하고 값 연결

		ans += weight;
		union_node(node1, node2);
		count_node++;
	}

	cout << ans;
	return 0;

}