[백준/Python] MooTube (Silver) 15591번

정답 풀이

import sys
from collections import deque
N, Q = map(int, sys.stdin.readline().split())


# make weighted graph
G = {n:deque() for n in range(1, N+1)}
for _ in range(N - 1):
    p, q, v = map(int, sys.stdin.readline().split())
    G[p].append((q,v))
    G[q].append((p,v))

for _ in range(Q):
    ki, vi = map(int,sys.stdin.readline().split())
    visited, queue, ans = [0]*(N+1), deque(), 0

    # BFS
    visited[vi] = 1
    for v, k in G[vi]:
        visited[v]  = 1
        queue.append((v, k))

    while queue:
        v, k = queue.popleft()
        
        if k >= ki:
            ans += 1
            for nv, nk in G[v]:
                if not visited[nv]:
                    visited[nv] = 1
                    queue.append((nv, min(k, nk)))

    print(ans)

 

 

시간 초과 풀이

import sys
from copy import deepcopy
from collections import deque
si = sys.stdin.readline
N, Q = map(int, si().split())

# 1. 그래프 만들기
graph = [[] for i in range(N+1)]
check = [set() for i in range(N+1)]
for i in range(N-1):
    p, q, r = map(int, si().split())
    graph[p].append([q, r])
    graph[q].append([p, r])
    check[p].add(q)
    check[q].add(p)

# 2. bfs를 사용할 수가 없는듯?? 가는 길만 탐색하는 것이 아니기 때문에 섞인다...
# 각각의 root를 q에 저장해 최소 USADO를 구한다. 
def bfs(start, end):
    q = deque()
    visited = [0 for i in range(N+1)]
    q.append([start, []])
    visited[start] = 1 # 방문처리
    while q:
        start, root = q.popleft()
        if start == end:
            return min(root)
        for idx, val in graph[start]:
            if visited[idx] == 1: continue

            new_root = deepcopy(root)
            new_root.append(val)

            q.append([idx, new_root])
            visited[idx] = 1 # 방문처리

for start in range(1, N+1):
    for i in range(start + 1, N+1):
        if i in check[start]: continue

        mini = bfs(start, i)
        graph[start].append([i, mini])
        graph[i].append([start, mini])

for i in range(Q):
    k, v = map(int, si().split())
    answer = 0 
    for x, y in graph[v]:
        if y >= k:
            answer += 1
    print(answer)

 

시간복잡도에서 많은 차이가 있는데 이는 구현 방법이 비효율적이기 때문이다.

시간초과 풀이에서는 start위치와 end의 위치를 알아야하므로 for문을 부득이 두번 돌릴 수밖에 없었다. 1번에서 3번으로 가는 경우, 1번에서 4번으로 가는 경우 등을 모두 나누어 판단해야했기 때문이다. 추가로 단순한 bfs로 구현을 할 순 없었으므로 경로 list를 추가해 그 중 가장 작은값을 return하도록 min 함수를 활용할 수밖에 없었다. 따라서 시간복잡도는 O(N^3 * bfs()) 정도 되므로 시간초과가 난 것이다. 

 

하지만 정답 코드의 경우 어차피 연결된 것이므로 min으로 담아가면서 계산해주었다.