[백준 1647] 도시 분할 계획

문제 풀이

 

문제를 요약하면 다음과 같다.

1. 마을을 연결해야 된다. 그런데 가능한 최소의 비용으로 만들고 싶다.

2. 그런데 마을을 하나의 마을로 연결하는 게 아니라 나는 두 마을로 쪼개고 싶다. 그래도 가능한 최소의 비용으로 하고 싶다.

 

마을을 하나의 최소한의 비용으로 연결하고 싶었다면 MST 알고리즘인 크루스칼 알고리즘을 사용하면 된다.

그런데 이 문제는 마을을 한 개가 아니고 두 개로 나누고 싶어하기 때문에 고민이 필요하다.

 

신기한 점은 MST를 이룰 때 노드의 개수가 N개면 최소한의 비용으로 연결하려면 간선의 개수는 N - 1개만 필요하게 된다. 예를 들어 노드 5개가 있을 때 4개의 간선만으로도 5개의 노드를 모두 연결할 수 있기 때문이다.

 

그러면 마을이 2개라면?

노드의 개수가 N개고, 간선의 개수는 N - 2개면 충분하다.

간선의 개수 N - 1개 까지는 마을 A에 연결시켜주고 마지막 간선만 딱 때어버리면 남겨진 마을이 곧 마을 B이기 때문이다.

 

가벼운 문제지만 살짝 깊이있는 질문을 하는 문제였다.

 

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX = 100001;
int N, M;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
int findParent(int x)
{
	if (x == parent[x]) return x;
	else return parent[x] = findParent(parent[x]);
}

void unionParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void input()
{
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({ c, {a,b} });
	}

	sort(edges.begin(), edges.end());
	for (int i = 1; i <= N; i++) parent[i] = i;
}

void solve()
{
	input();

	int ans = 0;
	int cnt = 0; // 간선 포함 개수
	for (int i = 0; i < edges.size(); i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (findParent(a) != findParent(b))
		{
			unionParent(a, b);
			ans += cost;
			cnt++;
			// 마지막 간선을 제외한다.
			if (cnt == N - 2)
				break;
		}
	}

	cout << ans << endl;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}