(c++)백준 15591번: MooTube (Silver)

www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

[풀이]

bfs를 사용하여 USADO가 k이상인 비디오의 개수를 세 주었다.

※query마다 visited배열을 false로 초기화해야한다.

 

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

struct Video {
	int v;
	int USADO;
};

int N, Q;
int p, q, r;
vector<Video>Moo[5001];
bool visited[5001];

//v와의 USADO가 k미만인 비디오 개수 반환
int bfs(int k, int v) {
	queue<int>q;
	q.push(v);
	visited[v] = true;
	int cnt = 0;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (int i = 0; i <Moo[v].size(); i++) {
			int nv = Moo[v][i].v;
			int nU = Moo[v][i].USADO;
			if (nU < k || visited[nv])
				continue;
			visited[nv] = true;
			cnt++;
			q.push(nv);
		}
	}
	return cnt;
}

int main() {
	cin >> N >> Q;
	for (int i = 0; i < N - 1; i++) {
		cin >> p >> q >> r;
		Moo[p].push_back({ q,r });
		Moo[q].push_back({ p,r });
	}
	int k, v;
	while (Q--) {
		for (int i = 1; i <= N; i++)
			visited[i] = false;
		cin >> k >> v;
		cout << bfs(k, v) << '\n';
	}
	return 0;
}