글 읽기 - 파이썬 BFS 시간 초과 질문입니다

raekim 2년 전 0

BFS 로 풀었는데 자꾸만 시간 초과가 납니다.

로직이 잘못되어 무한루프가 생긴건지, 파이썬 언어를 잘못 써서 시간 초과난 건지 모르겠네요. ㅜㅜ

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)

raekim 2년 전 0

동일한 코드를 언어설정을 Pypy3 로 해서 제출하니 맞았다고 뜹니다. 로직의 문제가 아니라 파이썬 언어 속도 문제였던 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 BFS 시간 초과 질문입니다

raekim 2년 전 0

raekim 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말