골드3 - 백준 16562 친구비

백준 16562 친구비

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

접근방법

문제에서 친구의 친구는 친구로 취급하기 때문에, 친구들을 그룹으로 나누어서 생각하였다. 그룹 속에 속해있는 친구 중 가장 친구비가 싼 친구를 선택하여 더해주었고, 전체 그룹과 친구가 되는 합계 비용을 구해주었다.

풀이

BFS를 이용하여 친구 그룹들을 탐색해주었고, Min_cost 변수에 가장 적은 친구비를 갱신해나간다. BFS가 끝나면 Min_cost를 total에 더해주고 아직 친구가 되지 않은 친구들을 탐색해가며 BFS를 진행시킨다.
최종적으로 total 값이 나오고 만약 total이 k원보다 적다면 total을 출력해주고 k원보다 크다면 "Oh no"를 출력해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int costs[10001];
vector<int> relation[10001];
bool visited[10001] = { false, };

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

	int N, M, k;
	cin >> N >> M >> k;

	for (int i = 1; i <= N; i++)
		cin >> costs[i];

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		relation[a].push_back(b);
		relation[b].push_back(a);
	}

	int total = 0;
	for (int i = 1; i <= N; i++)
	{
		if (visited[i])
			continue;
		queue<int> q;
		q.push(i);
		visited[i] = true;
		int Min_cost = costs[i];

		while (!q.empty())
		{
			int cur = q.front();
			q.pop();

			for (int j = 0; j < relation[cur].size(); j++)
			{
				if ( visited[relation[cur][j]] )
					continue;

				visited[relation[cur][j]] = true;
				q.push(relation[cur][j]);

				Min_cost = min(Min_cost, costs[relation[cur][j]]);
			}
		}

		total += Min_cost;
	}

	if (k >= total)
		cout << total << endl;
	else
		cout << "Oh no" << endl;
	return 0;
}