백준 1414 - 불우이웃돕기(C++)

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

1414번: 불우이웃돕기

최소 스패닝 트리를 이용한 문제입니다.

N*N의 입력으로 정점끼리 연결된 정보가 주어질 때, 기부할 수 있는 최대 전선의 길이를 구하는 문제입니다.

최대 전선의 길이를 구하기 위해선, 컴퓨터들끼리 연결시킨 전선의 최소 길이를 구한 뒤, 전체 전선의 길이에서 빼주면 됩니다.

문제에서 모든 컴퓨터가 연결되어 있어야하며, 다른 컴퓨터들을 통해 연결될 수 있다면 서로 통신할 수 있다는 것을 보아
최소 스패닝 트리를 이용해 모든 컴퓨터를 연결하면 됨을 알 수 있습니다.

최소 스패닝 트리를 이용해 최소 전선의 길이를 구했다면, 과연 모든 컴퓨터들이 연결되어 있는지를 확인해야합니다.

이는, MST를 실행하고 난 뒤, 연결된 모든 정점들을 Find함수를 통해 어디까지 연결되어 있는지를 확인해본다면
하나의 정점만을 가르키고 있다는 점을 이용해주면 됩니다.

N개의 정점이 모두 같은 정점으로 도착한다면 전부 연결된 것이며 아니라면 연결이 되지 않은 것 입니다.

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

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>

using namespace std;

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

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

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

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

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

bool check_connect(){
	int fin = Find(1);
	for(int i = 2; i <= N; i++){
		if(fin != Find(i)) return false;
	}
	return true;
}

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

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			char cost;
			cin >> cost;
			if(cost == '0') continue;
			if(cost >= 'a' && cost <= 'z'){
				connect.push_back({i, j, cost-'a'+1});
				length += (cost - 'a' + 1);
			}
			else{
				connect.push_back({i, j, cost-'A'+27});
				length += (cost - 'A' + 27);
			}			
		}
	}
	solve();
	return 0;
}

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