백준 1197번 최소 스패닝 트리 C++ MST, 최소 신장 트리

리뷰

MST의 기초가 되는 문제이다.

 

문제 풀이

1. 노드의 개수 v와 간선의 개수 e를 입력 받고 간선의 개수 만큼의 for문을 개행 한다.
2. 튜플 벡터 edges 를 초기화 해주고, 숫자 a, b, c를 입력 받은 후 c, b, a 순으로 튜플에 푸시 해준다.
3. edges 벡터를 오름차순으로 정렬 해준다, 이후 Union-Find를 통해 최소 신장 트리를 만들어 주면 된다.
4. 변수 sum을 0으로 초기화 하고 가중치를 기준으로 오름 차순으로 정렬 되어 있는 edges벡터를 순회를 돈다.
5. 만약 1번 인덱스와 2번 인덱스 요소의 루트 노드가 같다면 이미 간선이 추가되어 있는 상태이므로 continue
6. 아니라면 1번 인덱스와 2번 인덱스를 Union 해준 후 해당 간선의 가중치를 sum에 더해준다.
7. for문이 종료된 후 sum을 출력해 주면 된다.

 

참고 사항

구조체를 사용하면 compare 함수를 직접 구현해 주어야 하지만, 튜플이나 페어를 써주면 내장 함수를 통해 정렬을 쉽게 할 수 있다.

 

 

정답 코드

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

using namespace std;

int nodes[10001];
int v, e;

vector<tuple<int, int, int>> lst;

int Find(int a) {
	if (nodes[a] == a) return a;
	return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
	int rootA = Find(a);
	int rootB = Find(b);
	if (rootA == rootB) return;
	nodes[rootB] = rootA;
}

int main() {
	cin >> v >> e;

	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < e; i++) {
		int a, b, c; cin >> a >> b >> c;
		edges.push_back({ c, a, b });
	}
	sort(edges.begin(), edges.end());

	for (int i = 1; i <= v; i++) {
		nodes[i] = i;
	}

	int sum = 0;
	for (int i = 0; i < e; i++) {
		tuple<int, int, int> cur = edges[i];
		if (Find(get<1>(cur)) == Find(get<2>(cur))) continue;
		Union(get<1>(cur), get<2>(cur));
		sum += get<0>(cur);
	}
	cout << sum;
}