백준 15591 MooTube (Silver)

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

문제에서 그래프가 주어지는데, q개의 질문사항을 잘 해결하는 문제이다.
문제에서 요구하는 것을 간단히 말하면, 어떤 정점에서 다른 정점까지 비용중에 요구한 값보다 큰 간선을 찾는 것이다.
그런데 현재 간선의 비용보다 그 이전 간선 비용이 더 작다면 이전 간선으로 계산하면 된다.
그렇기 때문에 q개의 질문사항마다 bfs를 통해 각 정점들을 확인하고, 비용의 최솟값을 갱신하면서 요구한 비용보다 큰 정점이 몇개인지를 찾아주면 문제가 해결된다.

from collections import deque
import math
n,q = list(map(int,input().split()))
edges = []
graph = [[] for i in range(n+1)]
for i in range(n-1):
    a,b,r = list(map(int,input().split()))
    graph[a].append((b,r))
    graph[b].append((a,r))

def bfs(start,k):
    queue = deque([])
    queue.append((start,math.inf))
    visited = [0]*(n+1)
    cnt = 0
    while queue:
        x,xl = queue.popleft()
        visited[x] = 1
        if xl < k:
            continue
        for v,vl in graph[x]:
            if not visited[v]:
                visited[v] = 1
                if vl >= xl: ## 아래로 더 갈수 있는경우
                    queue.append((v,xl))
                    cnt += 1
                else: ## 최솟값 갱신인 경우
                    if vl >= k:
                        queue.append((v,vl))
                        cnt += 1
    return cnt

for i in range(q):
    k,v = list(map(int,input().split()))
    print(bfs(v,k))