[G4] 백준 16562번 친구비 C++ 너비 우선 탐색

리뷰

 

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

주어진 비용으로 친구를 모두 사귈 수 있는지 여부를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 노드의 개수를 저장할 변수
• m : 간선의 개수를 저장할 변수
• k : 사용할 수 있는 비용을 저장할 변수
• cost : 친구를 사귀는데 필요한 비용을 저장할 배열
• v : 노드 방문 여부를 저장할 배열
• edges : 간선의 인접 리스트를 저장할 벡터 배열

 

함수

1. bfs

int bfs(int sn) {
	queue<int> q;
	q.push(sn);
	int mn = cost[sn];
	v[sn] = true;

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

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			mn = min(mn, cost[nn]);
			q.push(nn);
		}
	}
	return mn;
}

 

친구의 친구를 확인하고, 친구비의 최소값을 구하는 함수

 

 

문제풀이

1. n, m, k값을 입력 받고, n개의 친구 비용을 입력 받아 cost배열을 초기화한다.
2. m개의 간선 정보를 입력 받아 edges배열을 초기화한다.
3. 변수 sum을 0으로 초기화 하고, 모든 친구를 순회한다.
4. 이미 방문한 친구라면 continue처리하고, 방문하지 않았다면 bfs함수에 친구 번호를 매개변수로 전달하여 호출한다.
5. bfs함수 내부에선 시작할 친구 번호를 변수 sn으로 입력 받는다.
6. 정수형 큐 q를 초기화하고, 초기값으로 sn을 push한다.
7. 변수 mn을 cost[sn]으로 초기화하고, v[sn]을 true로 방문처리한다.
8. q가 빌때까지 친구의 친구를 순회한다. 방문하지 않은 친구라면 방문처리 후 f를 증가시킨다.
9. 친구를 만날 때 마다 변수 mn에 친구 비용의 최소값을 계속 갱신해준다.
10. while루프가 종료되면 mn에 저장된 값을 리턴한다.
11. sum에 bfs함수의 결과를 더해주고, 모든 노드를 순회할때까지 탐색을 계속한다.
12. 탐색을 마친 후 sum이 k를 초과한경우 "Oh no"를, 아니라면 sum을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 너비 우선 탐색을 통해 그룹을 지어주면서 해당 그룹의 최소 비용을 리턴하는 전략을 사용했다.
2. 친구비가 최대 1억이므로 int범위 내에서 해결이 가능하다.

 

정답 코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

const int N = 10001;
int n, m, k;
int cost[N];
bool v[N];
vector<int> edges[N];

int bfs(int sn) {
	queue<int> q;
	q.push(sn);
	int mn = cost[sn];
	v[sn] = true;

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

		for (int nn : edges[cn]) {
			if (v[nn]) continue;
			v[nn] = true;
			mn = min(mn, cost[nn]);
			q.push(nn);
		}
	}
	return mn;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i) cin >> cost[i];
	
	while (m--) {
		int a, b; cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		if (v[i]) continue;
		sum += bfs(i);
	}
	
	if (sum > k) cout << "Oh no";
	else cout << sum;
}