[BOJ] 파이썬 2307번_골목길

문제링크: https://www.acmicpc.net/problem/1738

풀이

import sys
import math
input = lambda:sys.stdin.readline().strip()

n,m = map(int,input().split())
inf = math.inf
graph = [[] for _ in range(n+1)]
distance = [-inf for _ in range(n+1)]
router = [-1 for _ in range(n+1)]
for _ in range(m):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))

distance[1] = 0
for iter in range(n):
    for current in range(1,n+1):
        for next, cost in graph[current]:
            if distance[current] != -inf and distance[current] + cost > distance[next]:

                distance[next] = distance[current] + cost
                router[next] = current
                if iter == n- 1:
                    distance[next] = inf

res = [n]

if distance[n] != inf:
    current = n
    while current != 1:
        current = router[current]
        res.append(current)

    res.reverse()
    print(*res)
else:
    print(-1)

벨만 포드 알고리즘을 정확히 이해하게 되었던 문제였다.

우선 문제에서 말한 경우에 따라서는 최적의 경로라는 것이 존재하지 않는 상황이 발생 한다는 조건이 무엇인지가 핵심이다.

처음에는 단순히 음의 사이클(여기서는 양의 사이클) 이 존재하면 위 조건에 부합된다고 생각했다.

하지만 이는 틀린 답이었다.

음의 사이클이 존재한다고 해도, 해당 음의 사이클이 도착지점까지의 경로를 포함하지 않는다면, 여전히 최적의 경로가 존재한다.

따라서, 벨만 포드 알고리즘의 n-1번째 반복에서, 갱신되는 정점이 존재한다면, Inf값을 넣어준다.

모든 반복을 마친 후 결과 배열에서, inf값이 들어있는 정점은 사이클에 포함되는 정점을 의미한다.

따라서 도착지인 n번 정점이 inf인지 아닌지로 위 조건을 걸러낼 수 있따.