백준 11657 타임머신

🔗 백준 11657 타임머신 

📌오늘의 학습 키워드

• 벨만 포드 알고리즘

✨공부한 내용 본인의 언어로 정리하기

• 벨만 포드는 최적의 상황(다익스트라)를 포함하고 있다. 
• 벨만 포드는 다익스트라와 달리 모든 간선을 각 순환마다 확인한다. 
• 알고리즘
  • 모든 정점의 최단 거리를 sys.maxsize로 초기화 해줬다. 
  • for 정점의 수
    
    • for 간선의 수
      • 현재와 다음 정점, 간선 비용을 갖고 
      • 만약 다음 정점을 현재 비용 + 간선 비용이 다음 정점의 비용보다 작을 경우 업데이트 해줬다. 
      • 💣 음수 순환이 없다면 모든 정점 - 1 를 순환 할 동안 최단 거리가 구해져야 한다. 하지만 음수 간선이 있을 경우 무제한으로 거리를 줄일 수 있으므로 만약 정점 수 만큼의 순환에서도 거리가 업데이트 된다면 그건 순환이 있다는 뜻!

📚오늘의 회고

• • 무턱대고 백트래킹을 공부한 시점이라 또 백트래킹을 하려고 했다. 새롭게 벨만 포드 알고리즘을 공부했고, 다익스트라와의 차이점을 제대로 파악하려고 했다. 왜 정점 - 1 을 순환할 동안 최단 거리가 구해져야하는 지 이해하지 못해 추가적으로 찾아봤다. 

[🤓문제 해결 코드]

import sys


def bf(start):
    dist[start] = 0
    for i in range(1, N + 1):
        # 모든 간선 확인
        for j in range(M):
            current = edges[j][0]
            next = edges[j][1]
            cost = edges[j][2]

            if dist[current] != sys.maxsize and dist[next] > dist[current] + cost:
                dist[next] = dist[current] + cost
                # N번째 에서도 값이 갱신되면 음수 순환 존재
                if i == N:
                    return True
    return False


N, M = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

dist = [sys.maxsize] * (N + 1)

infinite_loop = bf(1)

if infinite_loop:
    print("-1")
else:
    for i in range(2, N + 1):
        if dist[i] == sys.maxsize:
            print(-1)
        else:
            print(dist[i])