[백준 16562] 친구비

문제

백준 16562

유형

• 유니온 파인드
• dfs

풀이

정해는 유니온 파인드를 이용해서 푸는 것으로 보이지만 나는 dfs로 풀이하였다.

일단 입력을 받고 친구관계를 양방향 그래프로 만들어 주었다. 그리고 1~n까지 for문으로 순회하면서 서로 연결된 친구들 중 비용이 가장 낮은 값을 받아와서 계속 더해주었다.

만약 처음에 입력받은 k값보다 작은값이 나오면 바로 출력하고 그렇지 않으면 비용이 부족한것이기 때문에 Oh no를 출력해주었다.

코드

#include <bits/stdc++.h>

using namespace std;
int n, m, k, cnt;
int arr[10001];
vector<int> adj[10001];
bool visited[10001];

void dfs(int d) {
	visited[d] = true;

	cnt = min(cnt, arr[d]);

	for (int x : adj[d]) {
		if (!visited[x]) dfs(x);
	}
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) cin >> arr[i];
	for (int j = 0; j < m; j++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}


	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			cnt = 10001;
			dfs(i);
			ans += cnt;
		}
	}
	if (ans > k) cout << "Oh no\n";
	else cout << ans;

	return 0;
}