문제 출처 : https://www.acmicpc.net/problem/11657
난이도 : 골드 4
문제 접근
1번 도시(노드) 에서 출발해서 다른 도시(노드)들로 가는 가장 빠른 시간을 구하는 문제라 가볍게 다익스트라 알고리즘을 적용하면 될 것 같다라고 생각했지만 아니다.
이 문제는 간선의 가중치가 음수이기 때문에 다익스트라 알고리즘 을 사용할 수 없고, 벨만 포드 알고리즘 이라는 것을 사용해야 한다.
벨만 포드(Bellman-Ford) 알고리즘
벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 가중치가 있는 그래프에서 사용할 수 있다. 그리고 방향-무방향 그래프 다 가능하다.
차이점은 간선의 가중치가 음수인 경우 사용 가능하다 라는 데에 있다.
그리고 음수 사이클이 있는지 없는지 유무도 벨만-포드 알고리즘을 통해 판별할 수 있다.
그래서 실전에서는 다음과 같은 의사결정을 통해 벨만포드 알고리즘을 선택하면 될 것 같다.
- start노드 에서 각 노드까지의 최단거리? -> 다익스트라
- 그런데 가중치가 음수? 음수 사이클? -> 벨만 포드 떠올리기.
벨만 포드 알고리즘 구현 아이디어
벨만-포드 알고리즘 구현 아이디어는 다음과 같다.
(노드의 개수가 N일때) "모든 간선을 N-1번 반복해서 확인하며, 더 짧은 경로가 있다면 거리 배열을 갱신한다."
마지막(N번째) 반복에서 또 갱신이 일어나면 음수 사이클이 존재한다고 판단한다.
여기서 갱신이란
기존에 알고 있던 최단 거리보다 더 짧은 경로를 발견했을 때, 그 거리 정보를 바꿔주는 것을 말한다.
그래프에 음수 사이클 이 없다면, 모든 정점까지의 최단경로는 최대 N-1 개의 간선만 거치면 완성된다.
그래서 N-1번 반복 후에는 더 이상 더 짧은 경로가 나타나지 않아야 정상이다.
그런데 마지막 N번째 반복에서 또 갱신이 일어난다는건 계속해서 거리가 줄어드는 음수 사이클 이 존재한다는 뜻이다.
음수 사이클이란?
음수 사이클이란 위 사진과 같이 사이클이 존재하고 사이클을 돌때마다 제자리로 돌아오면서 총 비용이 줄어드는 경로가 음수 사이클이다.
( 이미지를 GPT로 생성하며 새로 안 사실인데 이 음수 루프 이미지 생성을 요청했는데 계속 음수 사이클이 없는 이미지를 생성하길래, 혹시 AI는 음수 사이클이 포함된 이미지를 생성못하는 거냐 물어보니 제한적으로 생성되거나 왜곡될 수 있다고 한다. 이유는 부정적/무한 루프/게임 핵 등 악용 가능성이 있는 구조 때문이라고 한다.)
쨌든 벨만-포드를 쓰면 이 음수 사이클이 있는 그래프에서도 사용할 수 있고, 음수사이클이 있는 지 없는 지 판별가능하다고 한다.
벨만 포드 알고리즘 구현 절차
1. 최단 거리 배열 초기화
시작 정점을 제외한 모든 정점까지의 거리를 무한대(INF) 로 설정한다.
시작 정점의 거리는 0으로 설정한다.
2. N-1번 모든 간선 확인 & 거리 갱신
모든 간선을 하나씩 확인하며, 더 짧은 경로가 있으면 거리 배열을 갱신한다.
이 과정을 정점 수 N - 1번 반복한다.
(왜냐하면, 최악의 경우 한 정점까지 도달하는 데 최대 N-1개의 간선을 거칠 수 있기 때문)
3. 음수 사이클 판별
마지막 N번째 반복에서도 갱신이 일어난다면,
계속해서 거리가 줄어드는 음수 사이클이 존재한다는 뜻이다.
해답 및 풀이
import sys
input = sys.stdin.readline
INF = int(1e9)
# 입력
N, M = map(int,input().split())
edges = [] # 벨만 포드는 인접리스트나 행렬 방식이 아니라 어차피 다 N-1만큼 순회하기에 간선 정보룰 1차 리스트로 만든다.
for _ in range(M):
A, B, C = map(int,input().split())
edges.append((A, B, C))
# 벨만 포드 알고리즘 구현
def bellman_ford(N , edges):
# 1. 최단 거리 배열 초기화
distance = [INF] * (N + 1)
distance[1] = 0 # 시작 정점은 1번
# 2. N-1번 모든 간선 확인 & 거리 갱신
for _ in range(N - 1):
for A, B, C in edges:
if distance[A] != INF and distance[B] > distance[A] + C:
distance[B] = distance[A] + C
# 3. 음수 사이클 판별 N-1번 이후 1번더 돌았을 때 값이 줄어드는 경로가 존재한다? -> 음수사이클 존재한다. 판별
for A, B, C in edges:
if distance[A] != INF and distance[B] > distance[A] + C:
return None # 음수 사이클 존재
return distance
result = bellman_ford(N, edges)
# 출력
# 음수 루프 있다면 None 으로 정의 했었음
if result is None:
print(-1)
else:
for i in range(2, N + 1): # 시작 노드(1번)의 거리는 항상 0이기 때문에 출력 대상이 아님
if result[i] == INF:
print(-1)
else:
print(result[i])
다익스트라의 경우 간선들의 정보를
graph[u].append((v,w)) 이런식으로 인접 리스트로 받았지만
벨만 포드 알고리즘의 경우 간선의 정보를 그냥 edges = [] 로 배열을 선언하고
edges.append(u, v, w) 이런 식으로 받는다.
이유는 다익스트라는
현재 확정된 거리에서 인접한 노드들만 우선적으로 탐색하는 방식이라
인접 리스트 구조가 훨씬 효율적이다.
그러나 벨만-포드는
모든 간선을 매 반복마다 순회하며 거리 갱신을 시도하는 알고리즘이기 때문에 특정 정점에서 출발하는 간선만 탐색할 필요 없이, 그래프 전체의 간선을 단순히 나열한 리스트만 있으면 그걸 N-1번 돌면서 업데이트하면 되기 때문이다.
이를 간선 리스트 라고 한다.
다시 푼 코드
import sys
input = sys.stdin.readline
INF = int(1e9)
N, M = map(int,input().split())
edges = []
for _ in range(M):
A, B, C = map(int,input().split())
edges.append((A,B,C))
# edges [(1,2,4),(1,3,3),(2,3,-1),(3,1,-2)]
def bellman_ford(N, edges):
dist = [INF] * (N+1)
dist[1] = 0
for _ in range(N-1):
for A,B,C in edges:
if dist[A] != INF and dist[B] > dist[A] + C:
dist[B] = dist[A] + C
for A,B,C in edges:
if dist[A] != INF and dist[B] > dist[A] + C:
return False
return dist
distance = bellman_ford(N,edges) # distance[i] = 1번 노드부터 i번노드까지의 최단거리, 음수 사이클이 존재한다면 False
for i in range(2,N+1):
if distance is False:
print(-1)
sys.exit(0)
else:
if distance[i] == INF:
print(-1)
else:
print(distance[i])