[백준] 15591 MooTube (파이썬 Python)

 

문제 링크

 

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

15591번: MooTube (Silver)

 

 

문제 풀이

 

한 노드와 다른 노드 사이의 usado가 그 사이의 usado의 최솟값이라는 조건을 보고

처음에는 해당 조건을 활용해서 usado들을 모두 저장해놓고 결과를 구해야하나 했습니다.

그것보다는 bfs를 활용하여 노드를 하나씩 이동하며 usado를 최솟값으로 갱신하고

k보다 usado가 클 경우 결괏값을 1씩 증가시키는 것이 효율적일 것 같았습니다.

 

def bfs(k, v):
    visited = [0] * (n + 1)
    visited[v] = 1
    result = 0
    queue = deque([(v, 1e9)])
    while queue:
        v, usado = queue.pop()
        for n_v, n_usado in graph[v]:
            n_usado = min(usado, n_usado)
            if n_usado >= k and not visited[n_v]:
                result += 1
                queue.append((n_v, n_usado))
                visited[n_v] = 1
    return result

 

visited 체크를 해나가면서 중복 없이 모든 동영상에 대한 Usado를 확인할 수 있게합니다.

문제에서 주어진 하나의 노드에 대해 연결된 모든 노드를 확인하며 가중치를 최소값으로 갱신하고

해당 가중치가 k보다 크며, 노드를 방문하지 않았을 경우 추천되는 목록에 추가됩니다.

해당 노드에 대해 같은 작업을 반복하기 위해 queue에 넣어줍니다.

 

 

전체 코드

from collections import deque, defaultdict

def bfs(k, v):
    visited = [0] * (n + 1)
    visited[v] = 1
    result = 0
    queue = deque([(v, 1e9)])
    while queue:
        v, usado = queue.pop()
        for n_v, n_usado in graph[v]:
            n_usado = min(usado, n_usado)
            if n_usado >= k and not visited[n_v]:
                result += 1
                queue.append((n_v, n_usado))
                visited[n_v] = 1
    return result


n, q = map(int, input().split())
graph = defaultdict(list)
for _ in range(n - 1):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
    graph[b].append((a, w))
for _ in range(q):
    k, v = map(int, input().split())
    print(bfs(k, v))