[BOJ] 15591

문제

me

import sys
from collections import defaultdict
input = sys.stdin.readline
INF = int(1e9)

N,Q = map(int,input().split())
maps = defaultdict(list)

for _ in range(N-1):
    p,q,r = map(int,input().split())
    maps[p].append((q,r))
    maps[q].append((p,r))

def dfs(k,v):
    visited=[False]*(N+1)
    stack = [[v,INF]]
    cnt=0
    while stack:
        cur, dist = stack.pop()
        if not visited[cur] and dist >=k:
            visited[cur]=True
            cnt+=1
            stack.extend(maps[cur]) # 연결된 동영상들 확인
    return cnt-1

for _ in range(Q):
    k,v = map(int,input().split()) # 최소 유사도, 현재 보고 있는 동영상
    print(dfs(k,v))

• 연결된 동영상들의 거리?가 k이상인 것을 찾으면 된다.
• 연결된 것 중 가장 거리가 짧은 것이 그 연결의 유사도라고 해서 처음엔 다익스트라로 최소 경로를 다 구했다.
• 하다보니 결국 연결된 것들은 시작 노드와 연결된 거랑 다름 없으니깐 중간 노드들과 거리가 k이상인 것을 찾으면 된다.
• 연결된 네트워크의 길이가 아니라 각각의 길이에 대해서라면 dfs를 이용하는 것이 좋을 것 같다.