백준 21924번 도시 건설 C++ MST, 최소 신장 트리

리뷰

최소 신장 트리가 완성 되었는지의 체크 시 간선의 개수를 n개로 했다가 틀렸다 ㅠ

최소신장트리가 잘 만들어 졌는지 체크가 필요한 문제

 

문제 풀이

1. 노드의 개수는 최대 10만이므로 nodes 배열을 100001크기로 생성해 준다.
2. n, m값을 받아주고 각 간선의 정보를 가중치, 시작 노드, 도착 노드의 튜플 형태로 edges 벡터에 받아준다.
3. 모든 도로를 연결 했을때의 도로의 가중치를 알아야 하므로 max_sum 변수에 가중치를 모두 더해준다.
4. edges벡터를 오름차순으로 정렬해 준 후 각 노드를 자기 자신을 value 값으로 갖게 끔 초기화 해준다.
5. sum과 sum_cnt를 0으로 초기화 해주고 edges 배열을 순회하여 Union-Find를 통해 최소 신장 트리를 만들어 준다.
6. 만약 sum_cnt가 n - 1 크기가 되었다면 최소 신장 트리가 잘 만들어 진 것이다, max_sum - sum 출력
7. 그렇지 않다면 스패닝 트리가 만들어지지 않았으므로 -1을 출력해 주면 된다.

 

참고 사항

가중치의 최대값이 100만, 간선의 개수의 최대가 50만 이므로 max_sum이 최대 5000억이 될 수 있다, sum 역시 int 타입의 범위를 벗어날 수 있으므로 long long 타입을 사용해 주도록 하자.

 

 

정답 코드

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

using namespace std;

int nodes[100001];
int n, m;

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 >> n >> m;

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

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

	long long sum = 0, sum_cnt = 0;
	for (int i = 0; i < m; 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);
		sum_cnt++;
	}
	if (sum_cnt == n - 1) cout << max_sum - sum;
	else cout << -1;
}