[백준] 2611번 자동차경주 파이썬 코드

코드

# 유향 비순환 그래프, 길 정렬 -> 위상정렬 사용
# 갈 수 있는 곳의 비용을 하나 하나 다 따져주어야 한다
# 때문에 진입차수가 0이 아니더라도 비용 최신화

from collections import deque
import sys
input = sys.stdin.readline

def topol_sort():
  queue = deque([1]) # 1부터 시작
  while queue:
    pn = queue.popleft()
    for i in graph[pn]:
      indegree[i[0]] -= 1 # 진입차수 -1
      cost = visited[pn]+i[1]
      if cost > visited[i[0]]: 
        visited[i[0]] = cost
        chase[i[0]] = pn # 가장 높은 값으로 초기화될 때 pn을 기록
      if indegree[i[0]] == 0 and i[0] != 1: # 1로 다시 가면 종료해주어야하기 때문
        queue.append(i[0])
node = int(input())
edge = int(input())
graph = [[] for _ in range(node+1)]
visited = [0]*(node+1)
indegree = [0]*(node+1)
chase = [0]*(node+1) # 역추적을 위한 리스트

for _ in range(edge):
  p,q,r = map(int, input().split())
  graph[p].append((q,r))
  indegree[q] += 1

topol_sort()
print(visited[1])
path = [1]
end = 1

while 1:
  end = chase[end]
  path.append(end)
  if end == 1: break
print(*path[::-1])

비용이 더 큰 값으로 업데이트 될 때 역추적 경로를 바꿔줘야하는데, 무조건적으로 교체해서 엄청 틀렸던 문제. 조건을 잘 봐야한다...