[백준 15591] MooTube (Silver) (C++)

문제 링크: https://www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

1. 주의할 점

- 시작하는 정점은 세지 않는다

 

2. 구현

- 그래프에 대한 정보를 V[] 벡터에 입력한다

- Query문 마다 Result, Visit[] 배열을 초기화하고 시작한다

- While문을 통해 방문하지 않은 Node중에서 간선의 값이 입력 받은 유사도의 값이상이면 큐에 추가하며 Result++한다

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct info {
	int idx, val;
};
info tmp;
vector<info> v[5001];
bool visit[5001];
int node, query, from, to, val, usado, start, result;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> query;
	for (int i = 0; i < node-1; i++) {
		cin >> from >> to >> val;
		tmp.idx = to;
		tmp.val = val;
		v[from].push_back(tmp);
		tmp.idx = from;
		v[to].push_back(tmp);
	}
	for (int i = 0; i < query; i++) {
		cin >> usado >> start;
		//초기화
		for (int j = 1; j <= node; j++)
			visit[j] = false;
		result = 0;
		visit[start] = true;
		queue<int> q;
		q.push(start);
		while (!q.empty()) {
			int cidx = q.front();
			q.pop();
			for (int j = 0; j < v[cidx].size(); j++) {
				int next = v[cidx][j].idx;
				if (visit[next]) continue;
				int nv = v[cidx][j].val;
				if (nv >= usado) {
					visit[next] = true;
					result++;
					q.push(next);
				}
			}
		}
		cout << result << '\n';
	}
	return 0;
}