백준_15591_MooTube (python)

★ 접근

 문제 지문에서 '네트워크 형태' + n과 q의 최대 크기를 미뤄봤을 때 그래프 문제인 것을 떠올렸고 처음에는 dfs로 풀었다가 시간초과가 발생했다. 입력 최대 크기가 백을 넘어가면 웬만하면 dfs를 사용하지 않는데도 불구하고 dfs를 사용했던 이유는 k,v가 입력으로 주어졌을 때 매번 v에 대해서 dfs 성질을 이용해야 된다고 생각했기 때문이다. 역시나 시간초과가 나왔고 bfs로 풀었다.

★ 풀이

 코드를 보면 어이가 없을 정도로 간단하다.

 매 입력에 대해서 방문하지 않은 노드이면서 현재 usado가 k보다 크거나 같다면 q에 추가(노선을 따라감) count(결과 값)를 1씩 늘린다.

 

★ 코드

from collections import deque
import sys
input = sys.stdin.readline
n,question = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(n-1):
    p,q,r = map(int,input().split())
    graph[p].append([q,r])
    graph[q].append([p,r])

def solve(k,v):
    count = 0
    q = deque()
    q.append(v)    
    visited = [0] * (n+1)
    visited[v] = 1
    while q:
        node = q.popleft()
        for next, usado in graph[node]:
            if not visited[next]:
                if k <= usado:
                    visited[next] = 1
                    q.append(next)
                    count += 1
    return count

for i in range(question):
    k,v = map(int,input().split())
    print(solve(k,v))

★ 회고

  bfs인 것을 알면서도 dfs로 풀었다. dfs를 택한 이유보다 bfs를 택하지 않았던 이유는 한 번 탄 노선에 대해서는 쭉 따라가야 한다고 생각했기 때문이다. bfs는 그것을 하지 못한다고 생각을 했고 하지만 문제는 k보다 큰 유사도만 개수를 구하는 거였기 때문에 굳이 한 노선을 깊게 파지 않아도 정답을 구할 수 있었다.