[BOJ]15591

BOJ 15591 - MooTube (Silver)

• 그래프, bfs를 이용해 풀이
• python3의 경우에는 속도 이슈가 존재하여 pypy3 사용
• N = 5000 → 그래프 깊이가 최대 5000일 수 있음 → 재귀 DFS는 위험하므로 bfs 이용

문제 풀이

N, Q = map(int, input().split())
n = [list(map(int, input().split())) for _ in range(N - 1)]
q = [list(map(int, input().split())) for _ in range(Q)]


from collections import defaultdict, deque

nodes = defaultdict(list)

for val in n:
    v1, v2, l = val[0], val[1], val[2]
    nodes[v1].append((v2, l))
    nodes[v2].append((v1, l))

def check(queue:deque, limit:int):
    global nodes 
    answer = set()
    visited = defaultdict(lambda : defaultdict(bool))


    while queue:
        curr = queue.popleft()
        for node in nodes[curr]:
            next, l = node[0], node[1]
            if not visited[curr][next]:
                visited[curr][next] = True
                if l >= limit:
                    answer.add(next)
                    queue.append(next)
    return answer

for c in q:
    limit, target = c[0], c[1]
    queue = deque([target])
    channels = check(queue, limit)
    if target in channels:
        channels.remove(target)

    print(len(channels))

테스트 케이스

n = [[1, 2, 3], [2, 3, 2], [2, 4, 4]]
q = [[1, 2], [4, 1], [3, 1]]