[baekjoon 21924] 도시 건설 (최소 스패닝 트리, 크루스칼, 유니온파인드) (C++)

https://www.acmicpc.net/problem/21924

21924번: 도시 건설

일반적인 최소 스패닝 트리를 찾는 문제였다.

하지만 문제를 제대로 안 읽고 급하게 푸느라 바로 정답을 맞히진 못했고 몇 가지 놓친 사항들이 있었다.

 

1. 수의 범위 (건물의 개수는 10^5개고, 도로의 비용은 최대 10^6이다.)

즉, int의 범위를 넘어간다.

 

2. 문제의 정답은 최소 가중치의 합이 아닌, 절약한 값을 출력해야 한다.

 

3. 최소 스패닝 트리가 완성이 되었어도, parent 배열은 업데이트되지 않는 경우가 있으므로

스패닝 트리가 완성이 되었는지 확인을 위해 find함수를 이용해서 비교와 동시에 parent 배열을 업데이트해주었다.

#include <iostream>
#include <queue>

using namespace std;

int N, M, from, to, weight;
long long total;
int parent[100001];
long long record[100001];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater< pair<int, pair<int, int>>> > pq;

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

bool unionParent(int a, int b, int weight) {
	a = getParent(a);
	b = getParent(b);

	if (a == b) {
		return false;
	}

	if (a > b) {
		parent[a] = b;
		record[b] += (record[a] + weight);
	}
	else {
		parent[b] = a;
		record[a] += (record[b] + weight);
	}
	return true;
}

bool find(int a, int b) {
	a = getParent(a);
	b = getParent(b);

	return a == b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;

	for (int n = 1; n <= N; n++) {
		parent[n] = n;
	}
	for (int m = 0; m < M; m++) {
		cin >> from >> to >> weight;
		total += weight;
		pq.push(make_pair(weight, make_pair(from, to)));
	}

	int answer = 0;

	while (!pq.empty()) {
		int w = pq.top().first;
		int vertex1 = pq.top().second.first;
		int vertex2 = pq.top().second.second;
		pq.pop();

		unionParent(vertex1, vertex2, w);
	}

	for (int i = 1; i < N; i++) {
		if (!find(i, i+1)) {
			cout << -1;
			return 0;
		}
	}
	if (total - record[parent[1]] > 0) {
		cout << total - record[parent[1]];
	}
	else
		cout << 0;
}