[C++] 백준 1368번: 물대기

문제 링크

1368번: 물대기

문제 요약

N개의 논에 물을 대는데, 물을 댈 때는 직접 우물을 파거나, 이미 물을 대는 다른 논에서 물을 끌어올 수 있다. 이때 모든 논에 물을 대는 최소 비용을 구해야 한다.

접근 방법

우물을 하나의 가상의 정점으로 생각하면 됩니다. 그래서 각 논에서 우물을 파는 비용을, 가상의 정점과 논 사이의 간선으로 생각할 수 있습니다. 그러면 간단한 최소 스패닝 트리 문제가 되어버립니다.

그래프 문제들 중에는 이렇게 자신이 간선과 정점을 추가로 정의해야하는 문제가 많이 있는 것 같습니다. 여러 점에서 출발 가능한 알고스팟의 소방차 문제같은 다익스트라 문제나, 정점 분할이 필요한 최대유량 문제들도 있습니다. 그런 문제들을 경험한 덕분에 보자마자 쉽게 푼 것 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Edge {
	int v1, v2, w;
	bool operator<(const Edge& a) { return w < a.w; }
};

const int MAX = 301;
int parent[MAX];
vector<Edge> edges;

int Find(int a) {
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void) {
	int n;
	cin >> n;

	for (int i = 0; i <= n; i++) parent[i] = i;

	for (int i = 1; i <= n; i++) {
		int w;
		cin >> w;
		edges.push_back({ 0, i, w });
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w;
			cin >> w;
			
			if (i == j)
				continue;

			edges.push_back({ i, j, w });
		}
	}

	sort(edges.begin(), edges.end());

	int ans = 0;
	for (auto& i : edges) {
		if (Find(i.v1) != Find(i.v2)) {
			ans += i.w;
			Union(i.v1, i.v2);
		}
	}

	cout << ans << '\n';
	return 0;
}