[백준] 15591번: MooTube (Silver)

문제

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

15591번: MooTube (Silver)

 

풀이

넓이우선탐색(BFS)을 사용해 풀었습니다.

그래프에는 시작 정점의 인덱스에 해당하는 리스트에 (도착 정점, 유사도)를 추가해줍니다.

갱신한 유사도가 k보다 크거나 같은 경우, 큐에 (다음 정점, 갱신한 유사도)를 넣고 유사도를 최소로 갱신시켜 나갑니다.

 

코드

파이썬

from collections import deque
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())

graph = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    p, q, r = map(int, input().split())
    graph[p].append((q, r))
    graph[q].append((p, r))

for _ in range(Q):
    k, v = map(int, input().split())
    count = 0
    queue = deque()
    visited = [False] * (N + 1)
    visited[v] = True
    queue.append((v, float('inf')))
    while queue:
        x, c = queue.pop()
        for nx, nc in graph[x]:
            nc = min(c, nc)
            if not visited[nx] and k <= nc:
                count += 1
                visited[nx] = True
                queue.append((nx, nc))
    print(count)