[백준 1738번] 골목길 (Python3)

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
graph = [[*map(int,input().split())] for i in range(M)]

DP = [-1e9]*(N+1); DP[1] = 0
path = [1]*(N+1); cycle = set()
for i in range(N):
  for u,v,w in graph:
    if DP[u]==-1e9:
      continue
    if DP[v] < DP[u]+w:
      DP[v] = DP[u]+w; path[v] = u
      if i==N-1:
        cycle.add(v)

DP2 = [-1e9]*(N+1); DP2[N] = 0
for i in range(N-1):
  for v,u,w in graph:
    if DP2[u]==-1e9:
      continue
    if DP2[v] < DP2[u]+w:
      DP2[v] = DP2[u]+w
      
fail = DP[N]==1e9
for c in cycle:
  if type(DP[c]+DP2[c]) == int:
    fail = True

if fail:
  print(-1)
else:
  result = [N]
  while result[-1]!=1:
    result.append(path[result[-1]])
  result.reverse()
  print(*result)

벨만포드 알고리즘 응용문제

벨만포드 알고리즘은 항상 실수를 유발하는 것 같다.

 

풀이를 설명하면,

1. 1번지점에서 모든 지점으로 벨만포드 알고리즘을 실행, 실행하면서 경로도 저장한다.

2. 만약 cycle이 존재하면, cycle이 존재하는 노드를 저장

3. N번지점에서 모든 지점으로 벨만포드 알고리즘을 실행, 그래프는 반대로 입력해야한다.

4. cycle이 존재하는 노드에 대해서 1번노드 >> 사이클노드 >> N번노드로 통하는 경로가 존재하거나 1>>N의 경로가 아예 없으면 -1 출력

5. 4번에 해당하지 않으면 저장한 path로 경로 출력

 

참고로 기여내역을 읽어보니 이 문제를 가중치에 -1을 곱하는 아이디어가 중요하다는 사람들이 많던데 벨만포드 알고리즘은 다 익스트라 알고리즘과 달리 가중치가 음수든 양수든 아무상관이 없어서 가중치에 -1을 곱하는 아이디어는 전혀 필요없다. (-1을 곱하지 말아야하는건 아니지만 그렇다고 굳이 곱할 필요도 없다는 것)

 

 

오늘의 교훈) 벨만 포드 알고리즘은 항상 실수를 주의하자