[Programmers] Python 프로그래머스 스타 수열(70130)

https://school.programmers.co.kr/learn/courses/30/lessons/70130

프로그래머스

 

 

음수간선이 존재하는 벨만포드 문제이다.

하지만, 음수 간선을 판별 혹은 음수 간선인 부분을 찾는 것이 아닌 음수 간선을 피해 값이 증가하는 방향으로 나아가 최대한 높은 값으로 도착지에 도착해야하는 문제이다. 

 

하지만, 만약 사이클이 존재하고, 마지막 도착 지점이 음수 간선 사이클이라면, -1을 출력하는 문제이다.

 

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
graph = []
distance = [-float('inf')] * (N+1)
put = [0] * (N+1)

for _ in range(M):
    s,e,cost = map(int,input().split())
    graph.append((s,e,cost))


def bf(start):

    distance[start] = 0

    for i in range(N):
        for s,e,cost in graph:
            if distance[e] < distance[s] + cost and distance[s] != -float('inf'):
                distance[e] = distance[s] + cost
                put[e] = s
                if i == N-1:
                    distance[e] = float('inf')

    if distance[N] == float('inf'):
        return -1

    k = N
    res = []
    while k != 1:
        res.append(k)
        k = put[k]
    res.append(k)
    res = res[::-1]
    return res

result = bf(1)

if result == -1:
    print(-1)

else:
    print(*result)

 

회고,

벨만 포드는 음수간선으로만 활용하는 방식만 알고 있었는데 새롭게 음수간선을 피하는 방법도 알게 되었다.