백준 1647 - 도시 분할 계획

문제 설명

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.

마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 집과 M개의 도로가 있을 때 이를 두 개의 그룹으로 나눈다.

두 그룹은 연결될 필요가 없지만 그룹안의 집들은 모두 연결되어 있어야 한다.

이러한 조건을 만족하도록 그룹을 나눴을 때 도로 비용의 합이 최소가 되도록 해야 한다.

 

우선, 문제를 그대로 생각해보면 N개의 그룹을 나누는 경우를 모두 구한 뒤 필요 없는 도로를 계산하고 총합을 구해야 한다.

번거로운 것과 더불어 시간 초과가 발생할 것이다.

하지만, 생각을 조금 바꿔보면 간단해 진다.

우선, 그룹 안에 집들은 모두 최소 비용으로 연결되어 있어야 한다.

그리고 두 그룹은 연결될 필요가 없다.

따라서, 모든 집을 최소 비용으로 연결한 뒤 가장 큰 가중치의 도로를 끊어버리면 된다.

즉, MST를 구한 뒤 최대 비용 간선을 끊으면 되는 것이다.

void MST()
{
	priority_queue<pair<int, int>> pq;
	vector<bool> visited(N + 1, false);
	pq.push({ 0, 1 });

	while (!pq.empty())
	{
		auto [dist, current] = pq.top();
		pq.pop();

		if (visited[current]) continue;
		visited[current] = true;
		included.push_back(-dist);

		for (auto [next, cost] : roads[current])
		{
			if (visited[next]) continue;
			pq.push({ -cost, next });
		}
	}
}

MST는 프림 알고리즘으로 구현하였다.

MST를 구한 뒤 정렬한 뒤 마지막 간선을 빼고 모두 더하면 답을 구할 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<vector<pair<int, int>>> roads;
vector<int> included;

void MST()
{
	priority_queue<pair<int, int>> pq;
	vector<bool> visited(N + 1, false);
	pq.push({ 0, 1 });

	while (!pq.empty())
	{
		auto [dist, current] = pq.top();
		pq.pop();

		if (visited[current]) continue;
		visited[current] = true;
		included.push_back(-dist);

		for (auto [next, cost] : roads[current])
		{
			if (visited[next]) continue;
			pq.push({ -cost, next });
		}
	}
}

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

	cin >> N >> M;
	roads.resize(N + 1, vector<pair<int, int>>());

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

		roads[a].push_back({ b,c });
		roads[b].push_back({ a,c });
	}

	MST();
	sort(included.begin(), included.end());


	int ans = 0;
	for (int i = 0; i < included.size() - 1; i++)
	{
		ans += included[i];
	}

	cout << ans;

	return 0;
}

---