백준 11657

<타임머신으로 빨리가기>

난이도: 골드 4

1. 백준 문제
   11657

2. 코드 알고리즘

• 벨만 포드 알고리즘 개념

• 11657번 슈도코드

3. 코드

#11657
#https://www.acmicpc.net/problem/11657

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

#그래프 에지 리스트
A = [[] for i in range(M)]

#거리 리스트
max = sys.maxsize #항상 maxsize 일정한 값?
D = [max]*(N+1)
result = False #음수사이클 존재 유무

#그래프 에지리스트 입력받기
for i in range(M):
    a, b, c = map(int, input().split())
    A[i].append((a, b, c))

#거리 리스트 출발노드에서 초기화
D[1] = 0
#다익스트라와 다른점 ~ 모든 에지를 순환한다!
for i in range(0, N-1):
    for j in range(0, M):
        node_now = A[j][0] #현재 에지 데이터 (출발 노드, 도착노드, 가중치)
        if D[node_now[0]] != max and D[node_now[1]] > D[node_now[0]] + node_now[2]:
            D[node_now[1]] = D[node_now[0]] + node_now[2]

#음수 사이클 확인
for i in range(0, M):
    node_now = A[i][0]
    if D[node_now[0]] != max and D[node_now[1]] > D[node_now[0]] + node_now[2]:
        result = True #음수 사이클 존재
        break

if result:
    print(-1)
else:
    for i in range(2, N+1):
        if D[i] == max:
            print(-1)
        else:
            print(D[i])

4. 코드 후기

• 벨만 포드 vs 다익스트라
  벨만 포드랑 다익스트라의 차이점을 비교하는 데 집중하자!
  다익스트라는 한번 방문하면 다시 방문하지 않는다. (다익스트라 알고리즘은 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다) 하지만, 가중치가 음수일 경우에는 여러번 방문해 최단 경로를 찾아야 된다. 그래서 벨만 포드를 적용해 가중치가 음수더라도 여러번 방문해 최단 경로를 찾는다.

• 출발 노드가 INF가 아닐때만 최단경로를 검사한다
  출발노드 INF란 거는 문제에서 주어진 시작 노드에와 연결이 안됐다는 얘기이므로 검사하면 안된다!!!

• 음수 사이클 존재할 경우
  음수 사이클이 존재하면 정답리스트가 무의미하고 최단거리 찾을 수 없느 그래프이다. 음수 사이클 존재시 무한하게 돌수록 가중치가 계속 감소하기 때문이다