처음에 MST인가? 라는 생각을 가졌는데 결국 이문제는 탐색을 해야하는 문제이다. 주어진 노드 관점에서 bfs를 진행해야 유사도를 측정해서 개수를 셀 수 있다.
유사도라는 것을 모든 연결들의 유사도중의 최솟값으로 정했으므로 노드와 노드사이의 거리가 k보다 작다면 방문자체를 할 필요가 없다.
import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
def bfs(start, k):
global graph
visited = [False] * (N+1)
q = deque()
q.append(start)
count = 0
while q:
now = q.popleft()
visited[now] = True
for n_n, w in graph[now]:
if not visited[n_n] and w >= k:
q.append(n_n)
count += 1
return count
N, Q = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
for _ in range(Q):
k, v = map(int, input().split())
print(bfs(v, k))
'알고리즘 > 백준' 카테고리의 다른 글
1195. 킥다운 (0) | 2022.06.09 |
---|---|
16968. 배열 복원하기 (0) | 2022.06.04 |
1914. 하노이 탑 (0) | 2022.04.27 |
10819. 차이를 최대로 (0) | 2022.04.24 |
17299. 오등큰수 (0) | 2022.04.11 |