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

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

15591번: MooTube (Silver)

bfs 또는 dfs로 해결할 수 있다.

쿼리가 최대 5,000개가 주어지고 정점도 최대 5,000개가 주어지므로

시간 복잡도 O(N*Q)로 해결할 수 있다.

 

각 쿼리마다 dfs를 돌리자.

동영상 추천은 USADO가 K를 넘어야 가능하므로,

현재 정점에서 다음 정점으로 가는 비용이 K를 넘는 경우만 가능하다.

그런 정점들의 개수에서 처음 시작한 정점의 개수를 고려한 1개를 빼주면 된다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
vector<pair<int,int>> graph[5050];
int dfs(int k, int cur, int before){
    int cnt=1;
    for(auto[next,cost] : graph[cur])
        if(next!=before && cost>=k)
            cnt += dfs(k,next,cur);
    return cnt;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1; i<n; i++){
        int a,b,c; cin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    while(q--){
        int k,v; cin>>k>>v;
        cout << dfs(k,v,-1)-1 << '\n';
    }
    return 0;
}

시간을 더 줄일 수 있는 해결 방법이 있다.

현재 이 해결 방법을 쿼리에 따라 반복된 작업이 자주 일어난다.

하지만 유니온 파인드와 오프라인 쿼리를 사용하면 반복된 작업을 하지 않고 해결할 수 있다.

[c++] 백준 15586 MooTube (Gold)는 이 풀이를 사용해야 해결할 수 있다.