백준 1368 - 물대기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1368

1368번: 물대기

최소 스패닝 트리를 이용하는 문제였습니다.

N개의 논에 물을 대려고 할 때의 최소 비용을 구하는 문제입니다.

논에 물을 대는 방법은 2가지가 있습니다.
1. 논에 우물을 파는 방법
2. 물이 있는 다른 논에서 자기 논으로 대는 방법

다른 최소 스패닝 트리 문제와 달리 다른 정점과의 간선 뿐만 아니라, 자기 자신의 값이 추가되었습니다.

하지만, 생각을 다르게 해본다면 논에 우물을 판다는 것을 미지의 논에서 물을 대는 방법으로 생각해보면 문제를 쉽게 풀 수 있습니다.
예를 들어, 존재하지 않는 0번이라는 우물에서 1 ~ N까지의 연결된 간선을 논에 우물을 파는 방법으로 바꾼다면, 의미는 같지만 더욱 쉽게 바뀌었습니다.

이를 구했다면, 최소 스패닝 트리를 이용해 최소 비용을 구해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define F first
#define S second

using namespace std;

typedef struct info{
	int x;
	int y;
	int cost;
}info;
int N;
int parent[301];
vector<info> connect;


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

bool cmp(info a, info b){
	if(a.cost < b.cost) return true;
	else return false;
}

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

void Union(int x, int y){
	if(x != y) parent[x] = y;
}

void solve(){
	reset_parent();
	sort(connect.begin(), connect.end(), cmp);
	int cost = 0;
	for(int i = 0; i < connect.size(); i++){
		int x = Find(parent[connect[i].x]);
		int y = Find(parent[connect[i].y]);
		if(x != y){
			Union(x, y);
			cost += connect[i].cost;
		}
	}
	cout << cost;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		int cost;
		cin >> cost;
		connect.push_back({0, i, cost});
	}
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			int cost;
			scanf("%d", &cost);
			if(cost == 0) continue;
			connect.push_back({i, j, cost});
		}
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.