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

15591번: MooTube (Silver)

 

 

N과 Q가 각각 최대 5000이므로 주어지는 쿼리마다 매번 bfs를 수행해도 시간에 늦지 않을 것이라고 생각했다.

 

시작점에서 bfs를 수행하면서 다음 영상과의 유사도(USADO)가 K보다 작은 경우 다음 영상은 추천되지 않는다고 생각하면 편하다. K보다 큰 경우에만 다음 영상의 번호를 큐에 넣으면서 bfs를 수행하고 그 수를 카운팅을 해준다면 매 쿼리마다 답을 구할 수 있게 된다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, Q;
 
vector<pii > adj[5001];
 
void input(){
    cin >> N >> Q;
    int p, q, r;
    for(int i = 0; i < N-1; i++){
        cin >> p >> q >> r;
        adj[p].push_back({r, q});
        adj[q].push_back({r, p});
    }
}
 
int bfs(int k, int v){
    int cnt = 0;
    
    bool visited[5001];
    memset(visited, 0, sizeof(visited));
    visited[v] = true;
    
    queue<int> que;
    que.push(v);
    
    while(!que.empty()){
        int now = que.front();
        que.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i].second;
            int next_road = adj[now][i].first;
            
            if(visited[next]) continue;
            if(next_road < k) continue;
            
            cnt++;
            visited[next] = true;
            que.push(next);
        }
    }
    
    return cnt;
}
 
void solve(){
    int k, v;
    for(int i = 0; i < Q; i++){
        cin >> k >> v;
        cout << bfs(k, v) << "\n";
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}