BOJ 1368 : 물대기

#BOJ 1368 : 물대기

1368번: 물대기

#풀이

문제를 읽다가 그리디로 풀어야 겠다는 생각을 했다.

 

한 우물은 무조건 파져야 하므로 가장 적은 비용의 우물을 파는 논을 저장하고

 

가장 최소 비용으로 연결하는 논들을 찾아가며 마지막에 우물파는 비용을 더했는데 틀렸다.

 

그 이유는 모든 논이 다른 논과 연결하는 것보다 우물파는게 더 비용이 싸다면 모든 논이 우물을 파야 하는데 나의 코드는 그러지 못했다... ㅜㅜ

 

쉽게 말해서 논에서 우물을 파는 비용 W가 모두 1 이고 

논과 논을 있는 비용 W가 2이면

 

모든 논은 우물을 파는게 가장 적은 비용이지만 내가 구현한 코드는 모든 논을 연결한 다음 한 논만 우물을 파서 가장 적은 비용이 아니다.

 

크루스칼 알고리즘을 사용하여 최소 신장 트리를 구현하였다.

 

#코드

#include<iostream>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
int n;
tuple<int, int, int> edge[100005];
vector<int> p(302, -1);
int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}
bool is_diff_graph(int a, int b) {
	int u = find(a); int v = find(b);
	if (u == v) return 0;
	if (p[u] == p[v]) p[u]--;
	if (p[u] < p[v]) p[v] = u;
	else p[u] = v;
	return 1;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	int idx = 0;
	for (int i = 1; i <= n; i++) {
		int w;
		cin >> w;
		idx++;
		edge[idx] = { w, i, n + 1 };
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w;
			cin >> w;
			if (w == 0)
				continue;
			idx++;
			edge[idx] = { w, i, j };
			
		}
	}
	int ans = 0;
	int cnt = 0;
	sort(edge + 1, edge + 1 +idx);
	for (auto nxt : edge) {
		int w, i, j;
		tie(w, i, j) = nxt;
		if (is_diff_graph(i, j) == 0) continue;
		ans += w;
		cnt++;
		if (cnt == n) break;
	}
	for (int i = 1; i <= n+1; i++)
		cout << p[i] << "z\n";
	cout << ans << '\n';
	return 0;
}