본문 바로가기
Problem Solving/Python

[백준]BOJ 15591: MooTube(Sliver) - Python/BFS

by Kellang 2024. 4. 12.

15591번: MooTube (Silver) (acmicpc.net)

 

15591번: MooTube (Silver)

농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의

www.acmicpc.net

문제

풀이

문제가 쓸데없이 복잡하게 설명되어 있다. 중요한 것은 모든 노드가 연결되어 있고 웨이트를 가진 엣지가 존재하지만, 두 노드간의 거리는 경로상의 가장 작은 웨이트를 가진 엣지가 된다.

 

따라서 웨이트가 있다 해서 다익스트라를 쓸 필요가 없다. 들어오는 쿼리마다 BFS를 이용하여 그래프를 탐색하고 두 노드간의 거리는 실시간으로 업데이트 해주면 된다.

 

코드

from collections import deque

def bfs(k, v):
    queue = deque()
    queue.append((v, 987_654_321))
    isVisited = [False] * (n + 1)
    isVisited[v] = True
    answer = 0

    while queue:
        cur_node, cur_usado = queue.popleft()
        for next_node, next_usado in graph[cur_node]:
            if isVisited[next_node]:
                continue
            if cur_usado < next_usado:
                next_usado = cur_usado
            if next_usado >= k:
                queue.append((next_node, next_usado))
                isVisited[next_node] = True
                answer += 1
    print(answer)

n, q = map(int, input().split())
graph = {}
for _ in range(n - 1):
    pi, qi, ri = map(int, input().split())
    if pi in graph:
        graph[pi].append((qi, ri))
    else:
        graph[pi] = [(qi, ri)]
    if qi in graph:
        graph[qi].append((pi, ri))
    else:
        graph[qi] = [(pi, ri)]

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