글 읽기 - python 시간초과 질문입니다 ㅠㅠㅠ 도무지 원인을 알 수가 없네요

brian990614 1년 전 0

30퍼센트에서 계속 시간초과가 나는데 원인을 모르겠습니다. 시간초과가 날 만한 부분을 못찾겠습니다 ㅠㅠㅠ 고수님들 도와주십쇼!!!

import sys
import heapq

n=int(sys.stdin.readline())
m=int(sys.stdin.readline())
bus=[[]for _ in range(n+1)]
answer=[float('inf')for _ in range(n+1)]
queue=[]

for _ in range(m):
  a,b,c=map(int,sys.stdin.readline().split())
  bus[a].append([b,c])

start,end=map(int,sys.stdin.readline().split())
answer[start]=0
heapq.heappush(queue,[0,start,[start]])
while queue:
  this_cost,this_city,path=heapq.heappop(queue)
  for x in bus[this_city]:
    next_city,next_cost=x
    if(next_cost>=answer[next_city]):
      continue
    if(this_cost+next_cost<answer[next_city]):
      answer[next_city]=this_cost+next_cost
      heapq.heappush(queue,[this_cost+next_cost,next_city,path+[next_city]])
      if(next_city==end):
        total_path=path+[next_city]
print(answer[end])
print(len(total_path))
print(*total_path)

-----------------------------------수정------------------------------------
import sys
import heapq
from collections import deque

n=int(sys.stdin.readline())
m=int(sys.stdin.readline())
bus=[[]for _ in range(n+1)]
answer=[float('inf')for _ in range(n+1)]
save=[0 for _ in range(n+1)]
queue=[]
final=[]

for _ in range(m):
  a,b,c=map(int,sys.stdin.readline().split())
  bus[a].append([b,c])

start,end=map(int,sys.stdin.readline().split())
save[start]=start
answer[start]=0
heapq.heappush(queue,[0,start])
while queue:
  this_cost,this_city=heapq.heappop(queue)
  for x in bus[this_city]:
    next_city,next_cost=x
    if(next_cost>=answer[next_city]):
      continue
    if(this_cost+next_cost<answer[next_city]):
      answer[next_city]=this_cost+next_cost
      save[next_city]=this_city
      heapq.heappush(queue,[this_cost+next_cost,next_city])
print(answer[end])
get_result=deque()
get_result.append(end)
while get_result:
  v=get_result.popleft()
  final.append(v)
  if(v==start):
    break
  get_result.append(save[v])
print(len(final))
print(*final[::-1])

djm03178 1년 전 0

매 정점마다 그 정점까지의 최단경로 전체를 리스트로 저장해서는 리스트의 길이의 총합은 O(nm)까지 나올 수 있습니다. 길이 999의 경로가 만들어진 뒤 그 끝에서 다른 정점으로 거리 갱신을 99000 번 하는 경우를 생각해 보세요.

경로는 역추적을 통해서 나중에 만들어야 합니다.

brian990614 1년 전 0

답변 감사드립니다. 말씀드린대로 리스트를 활용하여 다음 경로를 저장한 뒤 다익스트라를 진행 후 역추적 하는 방식으로 수정해보았는데 그래도 시간초과가 납니다.

수정후의 코드처럼 역추적을 하면 안되는지 한번 봐주시면 감사하겠습니다!

djm03178 1년 전 4

57, 58번째 줄은 크게 의미가 없는 검사입니다. 어차피 59번째 줄에서 필요한 조건을 모두 검사하고 있기 때문입니다.

조건이 추가되어야 하는 부분은 54번째 줄 이후입니다. 우선순위 큐 내에는 같은 정점이 여러 거리를 가지고 다수 들어가있을 수 있기 때문에, 여기에서 answer[this_city] == this_cost인지 검사를 해주지 않으면 같은 정점이 나올 때마다 55번째 줄의 루프에서 여기에 달린 간선들을 전부 보게 되기 때문에 최악의 경우 간선의 개수의 제곱에 비례하는 수의 간선을 체크하게 됩니다.

brian990614 1년 전 0

앗 ㅎㅎ

54번째 줄 이후

if(answer[this_city]<this_cost):continue

조건 추가하여 해결했습니다. 감사합니다!!

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

문제

문제

출처

ICPC

python 시간초과 질문입니다 ㅠㅠㅠ 도무지 원인을 알 수가 없네요

brian990614 1년 전 0

djm03178 1년 전 0

brian990614 1년 전 0

brian990614 1년 전 0

djm03178 1년 전 4

brian990614 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말