[PS] BOJ 1865 / 웜홀
![[PS] BOJ 1865 / 웜홀](/content/images/size/w2000/2025/10/-------------9.png)
문제 링크: https://www.acmicpc.net/problem/1865
벨만-포드 알고리즘을 활용하는 문제입니다.
풀이
벨만-포드 이해하기
벨만-포드 알고리즘의 기본적인 설명은 이전 글을 참고해주세요.
벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 한 개의 정점에서 다른 모든 정점으로의 최단 경로를 계산합니다. 따라서, 출발점에서 도달할 수 없는 정점들에 대해선 경로가 계산되지 않으며, 이러한 정점들을 거치는 음의 사이클의 경우 탐색되지 않습니다.
그렇다면, 벨만-포드 알고리즘을 $1 \cdots N$의 모든 정점에 대해 모두 실행해줘야 할까요? $V$개의 정점과 $E$개의 간선을 가지는 그래프에서 벨만-포드 알고리즘은 시간 복잡도가 $O(VE)$이므로,
$N$개의 정점과 $M+W$ (편의상 $2M$으로 표기하겠습니다.) 개의 간선을 가지는 이 문제의 그래프에서 $N$개의 정점에 대해 벨만-포드 알고리즘을 모두 실행하는 방법은 $O(N^2 \times M)$의 느린 시간 복잡도를 가지며, 시간 초과를 받을 수 있습니다.
또 다른 방법으로, 출발점에서 도달할 수 없는 정점들에 대해서 최단 경로를 계산하지 못한다는 점에서 착안해 모든 출발점에 도달 가능한 상태에서 벨만-포드를 1회 계산할 수 있습니다.
간단하게, 가상의 $N+1$번 정점을 만들고, 이 정점에서 $1 \cdots N$까지의 모든 정점으로 0의 거리의 간선이 이어져 있다고 생각하면 됩니다. 이후, $N+1$번 정점을 출발점으로 설정해 벨만-포드 알고리즘을 실행하게 되면 모든 정점에 도달 가능한 상태가 되며, 모든 정점에서의 음의 사이클을 찾을 수 있습니다.
edges = []
distance = [0] * 501
def bellman_ford(V):
for i in range(1, V + 1):
distance[i] = 0
for _ in range(V - 1):
for s, e, t in edges:
if distance[s] + t < distance[e]:
distance[e] = distance[s] + t
# 음의 사이클 유무 판단하기: 최단경로는 V-1개의 간선으로 이루어진다고 가정.
for s, e, t in edges:
if distance[s] + t < distance[e]:
return True # 음의 사이클 존재
return False # 음의 사이클 없음
벨만-포드 구현
자세한 설명은 1865번의 질문 게시판을 참고해주세요.
전체 코드
input = open(0).readline
edges = []
distance = [0] * 501
def bellman_ford(V):
for i in range(1, V + 1):
distance[i] = 0
for _ in range(V - 1):
for s, e, t in edges:
if distance[s] + t < distance[e]:
distance[e] = distance[s] + t
# 음의 사이클 유무 판단하기: 최단경로는 V-1개의 간선으로 이루어진다고 가정.
for s, e, t in edges:
if distance[s] + t < distance[e]:
return True # 음의 사이클 존재
return False # 음의 사이클 없음
for _ in range(int(input())):
N, M, W = map(int, input().split())
edges.clear()
for _ in range(M):
s, e, t = map(int, input().split())
edges.append((s, e, t))
edges.append((e, s, t))
for _ in range(W):
s, e, t = map(int, input().split())
edges.append((s, e, -t))
print("YES" if bellman_ford(N) else "NO")
solution.py