글 읽기 - [python] 시간초과를 어떻게 해결하나요..?

doublejy715 4년 전 0

해당 문제를 다익스트라로 해결하려고 합니다.

채점을 해보니 시간초과로 뜨더군요...

제 생각에는 queue의 구현에 있어서 너무 많이 값이 push되어서 시간초과가 난것 같은데

혹시 최적화하는 방법이 있을까요?

import heapq

N, M = map(int,input().split())
data = []
# 데이터 정렬
for _ in range(M):
    x,y = map(int,input().split())
    if x > y:
        x, y = y, x
    data.append([x,y])

# 다익스트라 구현
dis = { _ : float('inf') for _ in range(N+1)}
dis[0],dis[1] = 0,0
queue = []
heapq.heappush(queue,1)
while queue: 
    node = heapq.heappop(queue)
    for A_i,B_i in data:
        if A_i == node:
            heapq.heappush(queue,B_i)
            if dis[B_i] > dis[A_i] + 1:
                dis[B_i] = dis[A_i] + 1

# 출력 조절
count = 0
lists = []
for j in range(M):
    if max(dis.values()) == dis[j]:
        lists.append(j)
        count += 1

print(min(lists),max(dis.values()),count)

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

문제

문제

출처

ICPC

[python] 시간초과를 어떻게 해결하나요..?

doublejy715 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말