15591. MooTube (Silver)

 

15591번: MooTube (Silver)

 

풀이

 bfs를 통해서 유사도를 탐색하도록 구현하여 해결할 수 있다. 질문이 주어지면 해당 동영상으로부터 bfs 탐색을 하여 각 동영상의 USADO를 구하여서 개수를 출력하도록 한다. 이때 질문에 중복된 동영상이 들어올때를 대비하여 플래그를 기록하는 리스트를 하나 만들어 동일한 동영상에 대한 bfs 탐색을 중복으로 하지 않도록 하였다.

 

코드

import sys
input = sys.stdin.readline
INF = float('INF')

# bfs 함수


def bfs(v):
    q = [(v, INF)]  # v번 동영상부터 시작
    visited = [False for _ in range(N+1)]  # 이번 bfs에서 방문 여부 체크
    visited[v] = True

    while q:
        nv, u = q.pop(0)  # nv: 다음 동영상, u: usado

        # next: nv번 동영상과 연결된 다음 동영상, nextU: nv번 동영상과 next번 동영상의 usado
        for (next, nextU) in path[nv]:
            if visited[next]:  # 이미 방문한 동영상일 경우 continue
                continue

            nextUsado = min(u, nextU)  # 현재까지 연결들의 최솟값을 기록
            q.append((next, nextUsado))
            # usado리스트에 v번 동영상부터 next번 동영상까지의 usado 최솟값 기록
            usado[v][next] = nextUsado
            visited[next] = True  # next번 동영상의 방문 여부 갱신


if __name__ == '__main__':
    N, Q = map(int, input().split())  # N: 동영상의 개수, Q: 질문의 개수
    check = [False for _ in range(N+1)]  # n번 동영상 bfs 여부
    usado = [[0 for _ in range(N+1)]
             for _ in range(N+1)]  # n번 동영상의 각 동영상에 대한 usado 기록
    path = [[] for _ in range(N+1)]  # 입력으로 주어지는 두 동영상 쌍의 usado

    for _ in range(N-1):
        p, q, r = map(int, input().split())  # 동영상 p, q와 usado에 해당하는 r
        path[p].append((q, r))  # path에 usado 기록
        path[q].append((p, r))

    for _ in range(Q):
        k, v = map(int, input().split())  # k: usado 기준, v: 동영상 번호

        if check[v]:  # 이미 bfs를 진행한 동영상이라면
            print(len([x for x in usado[v] if x >= k]))  # 바로 k 이상의 동영상 개수를 찾는다
            continue

        check[v] = True  # bfs를 진행했음을 기록하고
        bfs(v)  # 동영상 v에 대하여 bfs 진행
        print(len([x for x in usado[v] if x >= k]))  # k 이상의 동영상 개수를 찾는다