[백준 15591] MooTube (Silver)

문제

 

처음 작성한 코드

import sys

# graph = [정점 번호, 거리]
def search(k, node):
    result = 0
    visited = [False] * (len(graph.keys())+1)
    stack = graph[node][:]
    visited[node] = True

    # 정점과 인접해있는 노드에서 k이상이면 result++
    for s in stack: 
        visited[s[0]] = True
        if s[1] >= k:
            result += 1

    # 인접해있는 노드말고
    while stack:
        n, d = stack.pop()
        for i in graph[n]:
            if not visited[i[0]]:
                visited[i[0]] = True
                min_d = min(d, i[1])
                stack.append([i[0], min_d])
                if min_d >= k:
                    result += 1
    return result

n, q = map(int, sys.stdin.readline().split())
graph = {i+1: list() for i in range(n)}

for i in range(n-1):
    s, e, distance = map(int, sys.stdin.readline().split())
    graph[s].append([e, distance])
    graph[e].append([s, distance])

for _ in range(q):
    k, node = map(int, sys.stdin.readline().split())
    print(search(k, node))

1. for i in range(n-1) 에서 연결관계가 입력되는데 만약 1 2 3 이렇게 입력되면 "1과 2는 3의 길이로 연결되어있다." 이 뜻이다. 그러면 나는 graph를 dictionary형태로 초기화해놓은 상태에서 1: [2,3], 2:[1,3] 이렇게 쌍방으로 넣어주면서 탐색할 준비를 했다.
2. 처음에 일단 정점 번호 node에서 인접한 노드만 따져서 k랑 비교후 result값을 증가시켜줬다.
3. 그 후에는 인접하지 않은 노드를 깊게 들어가면서 min()함수를 통해 최소값을 구해 그 값과 k와 비교해줬다.

 

깨달은 점

• 그냥 풀었는데 풀렸다.. 그말은 즉슨 dfs인지 bfs인지 모르고 풀었다는 것.. 근데 푼것만 보면 dfs같은데 stack을 이용하면 bfs라고 하고.. 참 어렵다 !!!!
• python3으로 채점받으면 시간초과 나는데 pypy3으로 하니까 통과됐다.. 실제 코테에선 얄짤없겠지? ㅜ.ㅜ