백준 15591 MooTube (Silver)

문제

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

해결방법

주어진 k, v가 있다 k보다 크거나 같은 USADO를 카운팅하는 문제이다.

주어진 예제에서
1 -> 2 일때 3
2 -> 3일때 2
2 -> 4 일때 4이다

예제에서 k :4, v:1일때 0으로 나와있다 왜?
1에서 시작해서 1 -> 2 -> 4로해서 그럼 2 -> 4 값이 4이니 k<=으로 되지 않나?
아니다! 여기서 USADO는 갈 때마다 min을 갱신하는 것이다 그러므로 1에서 시작해서 1 -> 2 -> 4는 값이 min(3, 4)로 3이된다.

여기서 좋은 방법은 출발점에서 bfs를 하다가 조건을 다음 cost가 현재보다 클 경우만 queue에 담는 것이다 .

또 ! 이문제는 가장작은 값으로 갱신하지만 최단경로는 아니기에 dfs로도 가능하다.

주의

if (!visited[nx] && k <= cost) {  //  k <= cost로 할때  1 -> 2로갈때 비용이 3이면  2 -> 4로 갈때 비용이 4더라도 usaco이거 때문에 비용이 3으로 갱신된다 
                //그부분을 조금 유연하게 해주기 위해서 이렇게 가능하다 

풀이

#include <bits/stdc++.h>

using namespace std;


int n, q, k;
vector<pair<int, int>> a[5001];
bool visited[5001];
int bfs(int k, int v) {
    int ans = 0;
    memset(visited, 0, sizeof(visited));

    queue<int> q;
    q.push(v);
    visited[v] = 1;

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

        for (int i = 0; i < a[now].size(); i++) {
            int nx = a[now][i].first;
            int cost = a[now][i].second;

            if (!visited[nx] && k <= cost) {  //  k <= cost로 할때  1 -> 2로갈때 비용이 3이면  2 -> 4로 갈때 비용이 4더라도 usaco이거 때문에 비용이 3으로 갱신된다 
                //그부분을 조금 유연하게 해주기 위해서 이렇게 가능하다 
                visited[nx] = 1;
                q.push(nx);
                ans++;
            }
        }
    }

    return ans++;
}
int main() {

    cin >> n >> q;
    for (int i = 0; i < n - 1; i++)
    {
        int t1 = 0, t2 = 0, t3 = 0; cin >> t1 >> t2 >> t3;
        a[t1].push_back({ t2, t3 });
        a[t2].push_back({ t1, t3 });
    }

    for (int i = 0; i < q; i++) {
        int  v = 0; cin >> k >> v;   // vi를 보고 있는 소들에게 몇개의 동영상을 추천할꺼니 ? 
        cout << bfs(k, v) << endl;
    }
    return 0;
}