백준 11657번: 타임머신 (Python)

접근

최단 경로 참고 문제: 2021.04.14 - [코딩/백준 (Python)] - 백준 1753번: 최단경로 (Python)

백준 1753번: 최단경로 (Python)

기본적으로는 기존에 풀었던 최단 경로 문제에 음수 가중치를 더해주는 것 같이 보인다. 하지만 음수 가중치 때문에, 다익스트라 알고리즘을 이용할 수는 없고, 시작 노드에서 다른 모든 노드까지의 길이를 추적하는 벨만 포드 알고리즘을 이용해야 한다. (풀고 나서야 이것이 벨만 포드 알고리즘임을 알았다.)

다익스트라 알고리즘과 같이 힙정렬을 쓰지 않고, 시작 노드에서 각 노드까지의 거리를 담는 리스트를 작성해준다. 시작 노드의 거리를 0, 다른 노드에 대해서는 INF를 초기값으로 저장해준다. 시작 노드로부터 접근할 수 있는 모든 노드에 대해 거리를 계산해보고 더 작은 값으로 업데이트해나간다. 하지만 모든 노드의 경우의 수를 확인해도 계속 최소값이 갱신이 되면 음수 싸이클, 즉 시간을 무한히 오래 전으로 되돌릴 수 있다고 보고 -1을 출력해주면 된다.

코드

import sys

INF = float('inf')
n, m = map(int, sys.stdin.readline().split())
lines = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
bf = [INF] * (n + 1)


def solve_bf():
    bf[1] = 0
    minus = False
    for i in range(n):
        for j in range(m):
            v = lines[j][0]
            nv = lines[j][1]
            w = lines[j][2]
            if bf[v] != INF and bf[nv] > bf[v] + w:
                bf[nv] = bf[v] + w
                if i == n - 1:
                    minus = True
    if minus:
        print(-1)
    else:
        for k in range(2, n + 1):
            if bf[k] == INF:
                print(-1)
            else:
                print(bf[k])


solve_bf()

더 생각해 볼 것?

가끔 풀기만 하고 더 최적화된 코드 공부를 소홀히 하는 경우가 있는데 문제 푸는 것도 중요하지만, 문제를 풀면서 더욱 발전할 수 있도록 귀찮다고 느끼지 말고 부지런하게 공부를 해야겠다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!