BOJ 15591 MooTube / C++

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

15591번: MooTube (Silver)

백준 온라인저지 15591번 MooTube문제입니다.

 

아이디어

이 문제는 난이도의 비율이 문제 이해에 50%가 넘는 것 같았다. 문제만 이해한다면 풀이는 어렵지 않을 것 같네요.

네트워크 간선을 만들고 start 노드에서 출발하여 USADO이상을 가지는 간선들을 이동하여 카운팅하면 되는 문제인데요

bfs로 조건에 맞는 간선들을 돌며 모두 찾아낼 수 있다고 판단하여 bfs로 풀이 했습니다.

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

vector<pair<int, int>> adj[5001];
bool visited[5001];
int n, q;

void input() {
	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		//네트워크 간선 생성
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
	}
}

void bfs(int USADO, int start) {
	int cnt = 0;
	queue<int> q;
	q.push(start);
	vector<bool> visited(n + 1, false);
	visited[start] = true;
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		for (int i = 0; i < adj[current].size(); i++) {
			//방문 여부 체크
			if (visited[adj[current][i].first]) continue;
			//해당 노선의 USADO 확인
			if (adj[current][i].second < USADO) continue;
			visited[adj[current][i].first] = true;
			q.push(adj[current][i].first);
			cnt++;
		}
	}
	cout << cnt << "\n";
}

void solution() {
	int v, k;
	cin >> v >> k;

	bfs(v, k);
}
int main(void) {
	input();
	for (int i = 0; i < q; i++) {
		solution();
	}
}