[BOJ 15591] MooTube(Silver)

문제

[BOJ 15591] MooTube(Silver)

코드 1

USADO는 가는 경로 중 최솟값
그래프 탐색하면서 가중치 갱신하기
인접 리스트 방식 기억하기 !! graph[p].append((q,r))

import sys
input = sys.stdin.readline
from collections import deque
INF = int(10e9)+1

N,Q = map(int,input().split())
graph = [ [] for _ in range(N+1) ] # 1번부터 시작
for _ in range(N-1):
    p,q,r = map(int,input().split())
    graph[p].append((q,r))
    graph[q].append((p,r))
    
for i in range(Q):
    # 동영상 v에 대해 유사도가 k이상인 동영상의 개수를 찾기
    k,v = map(int,input().split()) 
    visited = [False]*(N+1)
    answer = 0
    
    q = deque()
    visited[v] = True
    q.append((v,INF))
    while q:
        node,node_cost = q.popleft() # node_cost는 node에서의 USADO(가는 경로 중 최솟값)
        # node의 USADO가 k이상이면
        if node_cost!=INF and node_cost>=k: answer += 1
        for (nxt,nxt_cost) in graph[node]:
            if not visited[nxt]:
                visited[nxt]=True
                if nxt_cost<node_cost:
                    q.append((nxt,nxt_cost)) 
                else:
                    q.append((nxt,node_cost)) 
                    
    print(answer)

코드2

가는 경로 중 최솟값이 유사도이기 때문에 nxt_cost가 k 이상인 경우만 보면 됨
k 미만인 경우는 유사도가 k 미만인 값이 되어버리니까

import sys
input = sys.stdin.readline
from collections import deque
INF = int(10e9)+1

N,Q = map(int,input().split())
graph = [ [] for _ in range(N+1) ] # 1번부터 시작
for _ in range(N-1):
    p,q,r = map(int,input().split())
    graph[p].append((q,r))
    graph[q].append((p,r))
    
for i in range(Q):
    # 동영상 v에 대해 유사도가 k이상인 동영상의 개수를 찾기
    k,v = map(int,input().split()) 
    visited = [False]*(N+1)
    answer = 0
    
    q = deque()
    visited[v] = True
    q.append((v,INF))
    while q:
        node,USADO = q.popleft() # USADO = node까지 가는 경로 중 최솟값
        for (nxt,nxt_cost) in graph[node]:
            nxt_USADO = min(USADO,nxt_cost)
            # 가는 경로 중 최솟값이 유사도이기 때문에 nxt_cost가 k 이상인 경우만 보면 됨
            # k 미만인 경우는 유사도가 k 미만인 값이 되어버리니까
            if nxt_USADO>=k and not visited[nxt]:
                answer += 1
                visited[nxt]=True
                q.append((nxt,nxt_USADO))
                    
    print(answer)