백준 21924 - 도시 건설(C++)

문제 링크입니다. https://www.acmicpc.net/problem/21924

21924번: 도시 건설

최소 스패닝 트리를 이용한 문제입니다.

모든 건물이 도로를 통해 연결되도록 할 때의 최솟값을 구하는 문제입니다.
다만, 모든 건물이 연결될 수가 없다면 -1을 출력해줘야 합니다.

모든 견물을 연결하는 방법은 최소 스패닝 트리를 통해 구해주면 됩니다.
문제는 전부 연결되어 있냐를 확인하는 방법입니다.

확인하는 방법은 최소 스패닝 트리의 원리를 생각하면 쉽게 떠올릴 수 있습니다.
MST를 하는 과정에서 정점이 연결된 곳을 계속 갱신해주는 것을 알고 있습니다.
하지만, 계속 갱신되는 것이 아닌 어느 정점을 도착점으로 잡고, 해당 정점을 끝으로 더 이상 갱신하지 않는 것을 알 수 있습니다.

그렇다면, 모든 정점의 연결된 곳의 끝을 찾는다면, 모두 연결된 도시의 경우에는 같은 정점을 나타날 것입니다.

해당 방법을 사용해, 만약 정점들이 다른 곳을 나타낸다면 한번에 연결되지 않는 것으로 생각해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define F first
#define S second

using namespace std;

int N, M;
typedef struct info{
	int x;
	int y;
	int cost;
}info;
vector<info> connect;
int parent[100001];
long long max_cost, min_cost;

bool cmp(info a, info b){
	if(a.cost < b.cost) return true;
	else return false;
}

void reset_parent(){
	for(int i = 1; i <= N; i++){
		parent[i] = i;
	}
}

void Union(int x, int y){
	if(x != y) parent[x] = y;
}

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

bool check_connect(){
	int fin = Find(parent[1]);
	for(int i = 2; i <= N; i++){
		if(fin != Find(parent[i])) return false;
	}
	return true;
}

void solve(){
	sort(connect.begin(), connect.end(), cmp);
	reset_parent();
	for(int i = 0; i < connect.size(); i++){
		int x = Find(parent[connect[i].x]);
		int y = Find(parent[connect[i].y]);
		if(x != y){
			Union(x, y);
			min_cost += connect[i].cost;
		}
	}
	if(check_connect()) cout << max_cost - min_cost;
	else cout << "-1";
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		connect.push_back({x, y, cost});
		max_cost += cost;
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.