[BOJ] Q15591 MooTube

[BOJ] Q15591 MooTube

Question

Language: Python

Difficulty: Gold 5

bfs 순회를 통해 해당 노드까지 도달하기까지의 최소 유사도값(간선의 가중치)를 갱신하면서 해당 값이 k보다 큰 경우에 대해서 count값을 증가시킨다.

N-1 개의 간선을 가지는 트리 형태의 그래프이므로 cycle이 존재하지 않으므로 특정 노드와 노드를 잇는 경로는 유일하다.

#현재까지의 최소 유사도
vertex,cost=queue.popleft()
#다음 노드에 대한 순회
for adj_vertex,new_cost in graph[vertex]:
    #유사도값 갱신
    temp_cost=min(cost,new_cost)
    #만일 갱신된 최소 유사도값이 k이상이면 해당 노드로 순회 진행
    if not visited[adj_vertex] and temp_cost >=k:
        count+=1
        queue.append((adj_vertex,temp_cost))
        visited[adj_vertex]=True

Solution

from collections import deque
from math import inf
def bfs(start,k):
    visited=[False] * (n+1)
    visited[start]=True

    queue=deque([(start,inf)])
    count=0
    while queue:
        vertex,cost=queue.popleft()

        for adj_vertex,new_cost in graph[vertex]:
            temp_cost=min(cost,new_cost)
            if not visited[adj_vertex] and temp_cost >=k:
                count+=1
                queue.append((adj_vertex,temp_cost))
                visited[adj_vertex]=True
    return count

def solution():
    for k,v in questions:
        print(bfs(v,k))

if __name__ == "__main__":
    n,q=map(int,input().split())
    graph=[[] for _ in range(n+1)]

    for _ in range(n-1):
        v1,v2,cost=map(int,input().split())
        graph[v1].append((v2,cost))
        graph[v2].append((v1,cost))

    questions=[list(map(int,input().split())) for _ in range(q)]
    solution()