백준 16562번: 친구비 (C++)

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

16562번: 친구비

 

풀이

유니온 파인드 연습용 문제.

 

비용이 작은 것을 부모로 연결하는 것이 중요하다.

 

map을 이용해서 부모가 같은 것들을 제외하고 최소 비용을 담아주었다. (연결된 친구 중 가장 작은 비용만 계산하면 되기 때문에 중복 제거가 필요했다.)

그리고 map을 돌면서 비용을 더해주며 k를 초과하는 지 체크해주었다.

 

다른 글을 찾아보니 다시 유니온을 해가며 더해주었던데 map이 너무 익숙해서 map으로 구현해봤다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int N, M, k;
int visited[10001] = { 0, };
int sum = 0;
vector<pair<int, int>> parent;
unordered_map<int, int> ump;

int Find(int x) { //부모 찾는 함수
	if (parent[x].first == x) return x;
	return parent[x].first = Find(parent[x].first);
}

void Union(int x, int y) { //비용이 작은 것을 부모로 연결
	x = Find(x);
	y = Find(y);
	if (x != y) {
		if (parent[x].second >= parent[y].second) parent[x].first = y;
		else parent[y].first = x;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> k;
	parent.push_back({ 0,0 });

	for (int i = 1; i <= N; i++) {
		int a;
		cin >> a;
		parent.push_back({ i,a });
	}

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		Union(a, b);
	}

	for (int i = 1; i <= N; i++) {
		Find(i); //부모 통일
		if(ump[parent[i].first]) ump[parent[i].first] = min(ump[parent[i].first], parent[i].second);
		else ump[parent[i].first] = parent[i].second;
	}

	for (auto i : ump) {
		sum += i.second;
		if (sum > k) {
			cout << "Oh no";
			return 0;
		}
	}
	cout << sum;
}