BOJ 15591번: MooTube (Silver)

문제

문제 바로가기> BOJ 15591번: MooTube (Silver)

15591번: MooTube (Silver)

 

풀이

BFS를 이용해 탐색을 진행하면서, USADO(가중치)가 k이상인지 검사 해주었다! 전체 경로에서의 최소값이 최종 USADO가 되므로, 가는 경로에서 가중치가 한번이라도 k이상이면 그 동영상은 추천 받을 수 없다.

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 5001
#define INF 1000000001
using namespace std;

int N, Q;
bool visited[MAX];
vector<pair<int, int> > path[MAX];

void input(){
    cin >> N >> Q;

    int p, q, r;
    for(int i=1; i<N; i++){ // 양방향 그래프
        cin >> p >> q >> r;
        path[p].push_back({q, r});
        path[q].push_back({p, r});
    }
}

void bfs(int k, int v){
    for(int i=1; i<=N; i++) visited[i] = false;
    visited[v] = true;

    int ans = 0;

    queue<int> q;
    q.push(v);

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

        for(int i=0; i<path[now_node].size(); i++){
            int next_node = path[now_node][i].first;
            int next_dist = path[now_node][i].second;

            if(visited[next_node]) continue;
            if(next_dist < k) continue;
            
            ans++;
            visited[next_node] = true;
            q.push(next_node);
        }
    }
    cout << ans << "\n";
}

void solution(){
    int k, v;
    while (Q--){
        cin >> k >> v;
        bfs(k, v);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}