[백준 1368] 물대기 (C++)

이 문제는 논에 물을 대는데 필요한 최소비용을 구하는 문제다. 그런데, 우물을 직접 파는 것과 다른 논에서 물을 끌어오는 방법이 있어, 최소 비용이 되도록 선택해야한다.

이 문제를 얼핏보면, MST를 구성하되 각 간선마다 물을 끌어오는 비용과 우물을 파는 비용중 최소인 경우를 선택하면 될 것 같다. 그래프가 항상 연결 그래프라면 이 아이디어가 맞겠지만, 그렇다는 보장이 없다. 연결 그래프가 아니라면, 탐색을 진행하다가 빠지는 정점들이 생긴다. 따라서, 분리집합에 대해 MST를 구성하는 과정을 반복하면 정답을 얻어낼 수 있겠지만, 구현이 너무 복잡해진다.

우리는 우물을 파는 것을 가상의 정점 $N + 1$로 바라보도록 하자. 모든 정점은 $N + 1$에 연결되어 있으므로 연결 그래프임이 보장된다. 그렇기 때문에, MST를 만들어낼 수 있다.

이제 크루스칼 알고리즘으로 문제를 해결해보자.

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

int n, p[302];
vector<tuple<int, int, int>> edge;

int find(int x) {
	if (p[x] == x) 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;
	for (int i = 1, w; i <= n; i++) {
		p[i] = i;
		cin >> w;
		edge.push_back({w, i, n + 1});
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1, c; j <= n; j++) {
			cin >> c;
			if (i >= j) continue;
			edge.push_back({c, i, j});
		}
	}

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

가상의 정점 $N + 1$때문에, 정점의 최대 갯수는 $301$개임을 유의하자. 이후, 간선들을 저장할 때, 우물을 파는 비용은 가중치가 w인 정점 i에서 가상의 정점 n + 1로 간주하고 저장하면 된다. 이후에는 인접 행렬의 형태로 논과 논을 연결하는 비용이 주어지지만, 무방향 그래프이므로 한쪽만 저장해주면 된다. 따라서, i >= j인 경우를 저장하지 않도록 코드를 작성했다.

덧붙혀, Union-Find에 사용할 대표 원소 배열 p는 간선 정보를 저장하면서 같이 초기화해줬다.

마지막으로 크루스칼 알고리즘으로 사이클이 생기지 않는 비용이 최소인 간선들을 $N$개 선택하면 된다. 왜냐하면, 우리는 가상의 정점 $N + 1$을 추가했기 때문에, 총 정점의 갯수는 $N + 1$개가 된다. 따라서, 간선을 $N$개 선택하고 종료하는 것이다.