[백준 1647] 도시 분할 계획 (C++)

이 문제는 마을 하나를 두 개로 분할한다. 이 때, 같은 마을에 속한 집들은 서로 연결되어있어야하며, 길의 유지비를 최소로 하도록 해야한다. 즉, 분리 집합 2개에 대해 각각 MST를 구하는 문제가 된다.

노드들을 어떻게 분할해서 분리 집합을 구성할지부터 의문이 들 것이다. 브루트포스는 경우의 수가 $N^2$이므로 시간 초과가 발생할 것이 자명하다. 따라서, 다른 방법을 고안해야 한다.

일단 마을 두 개를 구성할 때, 간선의 비용이 최소가 되야함은 확실하다. 따라서, 사이클이 생기지 않고 선택되지 않은 간선들을 중 비용이 최소인 것들을 선택해나가야 하는데, 이렇게 간선을 선택해나가다보면, 정점들이 속한 분리 집합의 갯수가 1개씩 줄어감을 확인할 수 있었다.
좀 더 자세히 설명하자면, 처음에는 정점이 개수와 동일한 $N$개의 분리 집합이 존재했다. 그리고 간선 하나를 선택해 둘을 이어주면, 정점 2개가 같은 분리 집합에 속하게 되어 분리 집합이 1개 줄어들게 된다. 즉, 총 분리 집합 갯수는 $N - 1$개가 된다.
정확히는 사이클이 생기지 않도록 간선을 중복되지 않게 선택해나가기 때문에, 항상 분리 집합의 갯수가 1개씩 줄게된다는 것이다.

따라서, 우리는 간선을 1개 선택할 때 마다 분리 집합 갯수가 1만큼 감소함을 파악할 수 있다.
그렇다면, 크루스칼 알고리즘으로 분리 집합의 갯수가 $2$가 될 때 까지 간선을 선택하면 유지비가 최소가 되도록 마을을 2개로 분할 할 수 있게 된다.

이를 코드로 옮기면 다음과 같다.

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

int n, m;
tuple<int, int, int> edge[1'000'000];
vector<int> p(100'001, -1);
long long ans;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	p[y] = x;
}

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

	cin >> n >> m;
	for (int i = 0, a, b, c; i < m; i++) {
		cin >> a >> b >> c;
		edge[i] = {c, a, b};
	}

	sort(edge, edge + m);
	for (int i = 0, a, b, c, cnt = n; i < m; i++) {
		tie(c, a, b) = edge[i];
		if (cnt == 2) break;
		if (find(a) == find(b)) continue;
		merge(a, b);
		ans += c;
		cnt--;
	}
	cout << ans;
}

다른 풀이로는 MST를 구한 다음, 간선 1개를 없애면 MST는 두 개의 분리 집합으로 분할된다. 하지만, 비용이 최소이기 위해서는 제거하는 간선은 비용이 최대인 간선이어야 한다. 이 아이디어를 이번엔 프림 알고리즘으로 구현해 보자.

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

priority_queue<tuple<int, int, int>,
			   vector<tuple<int, int, int>>,
			   greater<>> pq;

vector<pair<int, int> > adj[100002];
bool vis[100002];

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

	int n, m;
	cin >> n >> m;

	int a, b, c;
	while (m--) {
		cin >> a >> b >> c;
		adj[a].push_back({c, b});
		adj[b].push_back({c, a});
	}

	vis[1] = 1;
	for (auto nxt : adj[1]) pq.push({nxt.first, 1, nxt.second});

	int cnt = 0, ans = 0, mc = 0;
	while (cnt < n - 1) {
		tie(c, a, b) = pq.top();
		pq.pop();
		if (vis[b]) continue;

		vis[b] = 1;
		ans += c;
		mc = max(mc, c);
		cnt++;

		for (auto nxt : adj[b]) {
			if (!vis[nxt.second]) pq.push({nxt.first, b, nxt.second});
		}
	}
	cout << ans - mc;
}