(C++) 백준 15591. MooTube

백준 15591번 MooTube (C++)

---

문제 설명

• 특정 영상과의 유사도가 k 이상인 영상의 개수를 추천하도록 하는 문제.
• 영상 A에서 영상 B까지의 가는 경로 중 가장 유사도가 적은 값을 A<->B 영상간의 유사도로 결정한다.

---

문제 풀이##

• 예를 들어, 영상 A에서 출발해서 갈 수 있는 모든 경로를 탐색한다.
• 이때 영상 A에서 갈 수 있는 경로들에 대해 해당 경로에서의 유사도중 취소값을 방문 중인 영상과의 유사도로 저장한다.
• 경로 탐색을 위해서 dfs를 사용했다. (모든 경로에 대해 탐색을 해야하기 때문, bfs를 사용해도 무관)

---

코드

#include <iostream>
#include <vector>
using namespace std;
#define FOR(i,N) for(int i=1; i<=N; i++)
int N,Q;
vector<int> graph[5001];
int cost[5001][5001];
int vis[5001];
int ans = 0;
int usado = -1;
int result[5001];
void dfs(int s) {
    result[s] = usado;
    for(int i=0; i<graph[s].size(); i++) {
        if(vis[graph[s][i]] == 0) {
            vis[graph[s][i]] = 1;
            int n = usado;
            if(usado == -1 || usado > cost[s][graph[s][i]]) {
                usado = cost[s][graph[s][i]];
            }
            dfs(graph[s][i]);
            usado = n;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> Q;
    FOR(i,N-1) {
        int a,b,c; cin >> a >> b >> c;
        graph[a].push_back(b);
        graph[b].push_back(a);
        cost[a][b] = c;
        cost[b][a] = c;
    }
    FOR(i,Q) {
        ans = 0;
        usado = -1;
        FOR(j,N) {
            vis[j] = 0;
            result[j] = 0;
        }
        int k, v;
        cin >> k >> v;
        vis[v]=1;
        dfs(v);
        FOR(j,N) if(result[j]>=k) ans++;
        cout << ans << '\n';
    }
    return 0;
}