골드4 - 백준 1647 도시 분할 계획

백준 1647 도시 분할 계획

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

접근방법

마을을 두개로 분할하고 각 마을은 전부 연결되어 있기 위해서는 최소 스패닝 트리를 만족하는 경로에서 하나의 경로를 제외해주면 모두 연결된 두개의 마을로 분리된다. 따라서 문제의 조건인 최소 유지비를 구하기 위해서는 MST를 구하고 가장 비용이 큰 경로를 제외해주면 답을 구할 수 있다.

풀이

크루스칼 알고리즘을 이용하였고, union_find 함수를 이용하여 두개의 집이 이미 연결되어 있는지 확인해주었다. 사이클이 생기지 않는 경로들의 비용을 더해주었고 그 개수를 세어주었다. 그리고 N-2개의 경로가 선택될 때까지 반복적으로 수행해주었다. 최소 스패닝 트리가 생성되기 위해서는 N-1개의 경로가 필요하지만 그 중 가장 비용이 큰 거리를 빼주어야 하기 때문에 N-2개의 경로만 선택하여 그 유지비를 출력해주었다.

코드

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

using namespace std;

vector<pair<int, pair<int, int>>> route;
int city[100001];

int union_find(int node, int change)
{
	if (city[node] == node)
	{
		if (change == -1)
			return node;
		return city[node] = change;
	}

	return city[node] = union_find(city[node], change);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;

	for (int i = 0; i <= N; i++)
		city[i] = i;

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		route.push_back({ c, {a,b} });
	}

	sort(route.begin(), route.end());

	int cnt = 0;
	int cost = 0;
	for (int i = 0; i < route.size(); i++)
	{
		if (cnt == N - 2)
			break;

		int a = union_find(route[i].second.first, -1);
		int b = union_find(route[i].second.second, -1);

		if (a == b)
			continue;

		cnt++;
		cost += route[i].first;

		union_find(route[i].second.first, min(a, b));
		union_find(route[i].second.second, min(a, b));
	}

	cout << cost << endl;
}