[알고리즘] 35일차 (타임머신으로 빨리 가기) #백준11657번

08-5 벨만-포드

• 벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
• 기능: 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
• 특징: 음수 가중치 에지가 있어도 수행할 수 있음. 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
• 시간 복잡도(노드 수: V, 에지 수: E): O(VE)

[벨만-포드의 핵심 이론]
1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기

• 벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. 또한, 최단 경로 리스트를 출발 노드는 0, 나머지는 무한대로 초기화한다.

2. 모든 에지를 확인해 정답 리스트 업데이트하기

• 최단 거리 리스트에서 업데이트 반복 횟수는 "노드 개수 - 1"이다. 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다.
• 모든 에지 E = (s, e, w)에서 다음 조건을 만족하면 업데이트를 실행한다. 업데이트 반복 횟수가 K번이라면 해당 시점에서 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리이다.
• 업데이트 조건과 방법:
  D[s] != 무한대 이며 D[e] > D[s] + w일 때,
  D[e] = D[s] + w로 리스트의 값을 업데이트한다.
• 음수 사이클이 없을 때 N-1번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려 주는 정답 리스트가 완성된다.
• 이렇게 완성 후, 마지막으로 이 그래프에 음수 사이틀이 존재하는지 확인해야 한다.

3. 음수 사이클 유무 확인하기

• 음수 사이클 유무를 확인하기 위해 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인한다.
• 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다.
• 음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.
• 실제로 음수 사이클 판별하는 문제가 많이 출제되기 때문에, 마지막에 한 번 더 모든 에지르르 사용해 업데이트되는 노드가 존재하는지 확인하는 부분을 주목하자.

📌 문제 059) 타임머신으로 빨리 가기

시간 제한 1초, 골드 IV, 백준 11657번

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

3 4 # 노드, 에지
1 2 4
1 3 3
2 3 -4
3 1 -2

출력

 만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

-1

1단계 문제 분석

• 시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 것이다.
• 이렇게 시작점에서 다른 노드와 관련된 최단 거리를 구하는데, 에지가 음수가 가능할 때는 벨만-포드 알고리즘을 사용하면 된다.

1. 에지 리스트에 에지 데이터를 저장한 후 거리 리스트를 다음과 같이 초기화한다. 최초 시작점에 해당하는 거리 리스트 값은 0으로 초기화한다.
2. 벨만-포드 알고리즘을 수행한다.

[벨만-포드 알고리즘 수행 과정]
(1) 모든 에지와 관련된 정보를 가져온 후, 다음 조건에 따라 거리 리스트의 값을 업데이트한다.
(1-1) 출발 노드가 방문한 적이 없는 노드(출발 노드 거리 == INF)일 때 값을 업데이트하지 않는다.
(1-2) 출발 노드의 거리 리스트 값 + 에지 가중치 < 종료 노드의 거리 리스트 값일 때 종료 노드의 거리 리스트 값을 업데이트한다.
(2) "노드 개수 - 1"번만큼 (1)을 반복한다.
(3) 음수 사이클 유무를 알기 위해 모든 에지에 관해 다시 한번 (1)을 수행한다. 이때, 한 번이라도 값이 업데이트되면 음수 사이클이 존재한다고 판단한다.

3. 음수 사이클이 존재하면 -1, 존재하지 않으면 거리 리스트의 값을 출력한다. 단, 거리 리스트의 값이 INF일 경우에는 -1을 출력한다.

2단계 슈도 코드

N(슈도 코드) M(에지 개수)
edges(에지 정보 저장 리스트)
distance(거리 리스트) # 충분히 큰 수로 초기화

for 에지 개수만큼 반복:
	에지 리스트에 에지 정보 저장

# 벨만 포드 수행
거리 리스트에 출발 노드 0으로 초기화

for 노드 개수 - 1 만큼 반복:
	for 에지 개수만큼 반복:
    	현재 에지 데이터 가져오기
        if 출발 노드가 무한대가 아니고 종료 노드 값 < 출발 노드 값 + 에지 가중치:
        	업데이트 수행 -> 종료 노드 값 = 출발 노드 값 + 에지 가중치

for 에지 개수만큼 반복: # 음수 사이클 존재 여부 확인
	현재 에지 데이터 가져오기
    if 출발 노드가 무한대가 아니고 종료 노드 값 < 출발 노드 값 + 에지 가중치:
    	업데이트 가능 -> 음수 사이클 존재

음수 사이클 미존재 -> 거리 리스트 출력하기 # 단, 거리 리스트의 값이 무한대일 때 -1 출력
음수 사이클 존재 -> -1 출력

3단계 코드 구현

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
edges = []
distance = [sys.maxsize]*(N + 1)

for i in range(M): # 에지 데이터만 저장
    start, end, time = map(int, input().split())
    edges.append((start, end, time))

# 벨만 포드 수행
distance[1] = 0

for _ in range(N - 1):
    for start, end, time in edges:
        if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
            distance[end] = distance[start] + time

# 음수 사이클 확인
mCycle = False

for start, end, time in edges:
    if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
        mCycle = True

if not mCycle:
    for i in range(2, N + 1):
        if distance[i] != sys.maxsize:
            print(distance[i])
        else:
            print(-1)
else:
    print(-1)