백준 1865: 웜홀
https://www.acmicpc.net/problem/1865
문제 설명
N개의 지점과 M개의 도로, W개의 웜홀이 있다.
도로는 양방향, 웜홀은 단방향이며, 웜홀을 지나면 시간이 거꾸로 흐른다.
즉, 웜홀의 가중치는 음수로 표현된다.
이때, 그래프 어딘가에 “시간이 줄어드는 순환 경로(음수 사이클)” 가 존재한다면
“YES”를, 그렇지 않다면 “NO”를 출력해야 한다.
처음 접근: BFS 탐색
문제에서 “시간을 되돌리는 웜홀”이라는 문장을 보고 처음엔 단순하게 생각했다.
“모든 지점을 BFS로 돌면서, 시간이 줄어드는 루프가 생기는지 찾아보면 되지 않을까?”
그래서 처음 시도는 이렇게 했다:
- 도로와 웜홀을 각각 리스트로 분리해서 관리 (List<Node> roads, List<Node> wormholes)
- 각 지점을 시작점으로 BFS 탐색
- 시간이 더 짧아지는 경로(times[e] > times[s] + w)를 만나면 음수 사이클이라고 판단
하지만 문제가 생겼다.
BFS는 가중치가 일정하거나 양수일 때만 정상적으로 작동한다.
음수 가중치가 있으면 “방문했어도 다시 돌아가야 하는 경우”가 생기는데,
BFS는 이런 갱신을 반영할 수 없다.
그래서 시간이 과거로 가는 경우 방문했어도 다시 돌아가게끔 하는 방식을 생각했지만,
사이클이 발생했을 때는 무한대로 시간이 과거로 가기 때문에 대응할 수 없었다.
새로운 알고리즘: 벨만포드(Bellman-Ford) 알고리즘
이 문제의 핵심은 음수 사이클을 찾는 것이었다.
문제를 다시 읽어보면, 결국 출발점에 다시 되돌아왔을 때 시간이 더 과거이면 되는 것이었고,
결국 무조건 사이클이 발생하는 조건이어야 했다. 그것도 음의 사이클로만 발생해야 하는 것이다.
그 역할을 정확히 수행하는 알고리즘이 바로 벨만포드 알고리즘이다.
간략한 구조
- 다익스트라처럼, dist 배열을 만들어 출발점만 0, 나머진 무한대로 초기화
(단, 이 문제는 사이클만을 찾아야 하기에 모든 dist를 0으로 만들어야 한다.) - 모든 간선을 순회하며 (dist[시작점]이 무한대가 아니면서, dist[시작점] + 가중치 < dist[도착점]) 을 충족하면 값을 갱신하는 행위를 V−1번 반복
- 사이클을 찾기 위해, 모든 간선 순회를 1번 더 반복한다.
이 때 dist에 갱신이 일어난다면, 음수 사이클이 존재한다는 뜻이다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static class Edge {
int s;
int e;
int w;
public Edge(int s, int e, int w) {
super();
this.s = s;
this.e = e;
this.w = w;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
Edge[] edges = new Edge[M * 2 + W];
List<Edge>[] adjList = new List[N + 1];
int idx = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
edges[idx++] = new Edge(s, e, w);
edges[idx++] = new Edge(e, s, w);
}
for (int i = 0; i < W; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
edges[idx++] = new Edge(s, e, -w);
}
// 벨만-포드 알고리즘
System.out.println(bellmanFord(edges, N) ? "YES" : "NO");
}
}
private static boolean bellmanFord(Edge[] edges, int N) {
int[] dist = new int[N + 1];
Arrays.fill(dist, 0);
// 모든 간선을 순회 => N-1번 반복
// Why? 한 지점에서 다른 지점으로 갈 때 최소 거리는 사이클이 있지 않은 한, 최대 N-1개의 간선을 쓰기 때문
for (int i = 0; i < N - 1; i++) {
boolean updated = false;
for (Edge e : edges) {
if (dist[e.s] + e.w < dist[e.e]) {
dist[e.e] = dist[e.s] + e.w;
updated = true;
}
}
if (!updated)
break;
}
for (Edge e : edges) {
if (dist[e.s] + e.w < dist[e.e]) {
return true;
}
}
return false;
}
}개선 과정
1. 처음엔 모든 정점에서 벨만포드를 실행했다.
- 각 정점마다 bellmanFord(i) 호출
- 논리적으로는 맞지만, 시간복잡도 O(V²E) → 시간초과
2. dist 값을 모두 0으로 변경
- 최단거리를 구하는 게 목적이 아니라, 음수 사이클을 찾는게 목적이다.
- 따라서 굳이 출발점을 선택해가며 N번 순회할 필요 없이dist를 0으로 하는게 시간복잡도 상 이득이다.
- 시간복잡도 O(VE) 로 감소 → 통과
3. 조기 종료 최적화
- 한 라운드에서 갱신이 한 번도 없으면(updated == false),
모든 최단경로가 확정된 상태이므로 더 돌 필요 없음 → break
배운점
- BFS는 가중치가 음수일 땐 쓸 수 없다. 사이클에서 막히거나, 방문 체크에서 막힌다..
- 새로운 벨만 포드 알고리즘에 대해 알게 됐다.
- 다익스트라와 유사하지만, 음수 가중치일 때 사용할 수 있고, 사이클을 찾고자 할 때에도 사용할 수 있다!
- 음수 가중치 하나로 알고리즘 자체가 달라져 버린다는 것이 흥미로웠다.