[BOJ/Gold 2] 백준 1368 물대기(C++)

문제 링크

https://www.acmicpc.net/problem/1368

1368번: 물대기

 

문제

선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

입력

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.

출력

첫 줄에 모든 논에 물을 대는데 필요한 최소비용을 출력한다.

예제 입력 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

예제 출력 1

9

알고리즘 분류

• 크루스칼 알고리즘

풀이

우물을 팔 때 드는 비용 W와 논들 간의 물을 끌어오는 비용 P 두 가지의 가중치를 사용해야 한다.

가상의 정점 0을 만들어 N개의 정점과 연결하고 가중치를 우물을 팔 때 드는 비용 W로 한다. 그리고 정점 I, J 간에 물을 끌어오는 비용 P가 주어지면 두 정점을 I, J, 가중치를 P로 하는 간선으로 만든다.

마지막으로 최소 스패닝 트리를 만들어 가중치의 최솟값을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 301
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Start, End, Cost;
};

int N;
int Parent[MAX];
vector<INFO> Edge;
LL answer = 0;

void Init() {
	for (int i = 0; i <= N; i++) {
		Parent[i] = i;
	}
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX < PY) {
		Parent[PY] = PX;
	}
	else {
		Parent[PX] = PY;
	}
}

bool Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

void Input() {
	cin >> N;
	Init();
	for (int i = 1; i <= N; i++) {
		int W;
		cin >> W;
		Edge.push_back({ 0,i,W });
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int P;
			cin >> P;
			if (i < j) {
				Edge.push_back({ i,j,P });
			}
		}
	}
}

void Settings() {
	sort(Edge.begin(), Edge.end(), Comp);
	for (int i = 0; i < Edge.size(); i++) {
		int S = Edge[i].Start;
		int E = Edge[i].End;
		int C = Edge[i].Cost;
		if (Find(S) != Find(E)) {
			Union(S, E);
			answer += C;
		}
	}
}

void Find_Answer() {
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}