[BOJ/백준][Gold5] 15591 : MooTube (Silver) (C++)

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

15591번: MooTube (Silver)

 

 

[난이도] Gold5
[유형] DFS

[풀이]
N개의 점에서 모두 DFS를 해주며 dist[i][j] 배열에 i,j의 유사도를 저장해줍니다.
i와 j를 연결하는 경로는 한개씩밖에 없는 트리 구조의 그래프이기 때문에 재귀함수를 이용해
간단히 유사도를 구할 수 있습니다.
이때의 시간복잡도는 O(N*N) 입니다.

유사도를 모두 구해놨으므로 각 Q개의 쿼리에 대해 O(N)에 대응할 수 있으므로 이때의 시간복잡도는
O(N*Q) 입니다.

O(N*N)과 O(N*Q) 모두 O(5000*5000)으로 넉넉하지는 않지만 시간내에 해결이 가능합니다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,Q,dist[5001][5001];
vector<pair<int,int>> adj[5001];
bool visit[5001];
void dfs(int s,int prev,int cur,int v){
    for(auto [nxt,d] : adj[cur]){
        if(nxt!=prev){
            int t = min(v,d);
            dist[s][nxt]=t;
            dfs(s,cur,nxt,t);
        }
    }
}
int main(){
    scanf("%d%d",&N,&Q);
    for(int i=0;i<N-1;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    for(int i=1;i<=N;i++){
        dfs(i,-1,i,2e9);
    }
    while(Q--){
        int k,v,cnt=0;
        scanf("%d%d",&k,&v);
        for(int i=1;i<=N;i++){
            if(dist[i][v] >= k) cnt++;
        }
        printf("%d\n",cnt);
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/15591.cpp