문제
N개의 지점, M개의 도로(양방향), W개의 웜홀(단방향, 음의 가중치)이 주어질 때, 출발점으로 되돌아왔을 때 시간이 되돌려져 있는(음의 사이클) 경우가 있는지 판별하라.
입력
테스트 케이스 수 TC, 각 케이스에 N, M, W와 간선 정보가 주어진다.
출력
음의 사이클이 있으면 "YES", 없으면 "NO"를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8 | NO YES |
풀이
벨만-포드 알고리즘으로 음의 사이클 존재 여부를 판별한다.
- 도로는 양방향, 웜홀은 단방향 음의 가중치 간선으로 그래프를 구성한다
- N-1번 간선 완화를 수행한다
- N번째 완화에서도 거리가 줄어드는 간선이 있으면 음의 사이클이 존재한다
핵심 아이디어: 벨만-포드에서 N번째 반복에 갱신이 발생하면 음의 사이클이 있다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day471BOJ1865웜홀 {
static int N, M, W;
static int[] dist;
static ArrayList<ArrayList<Road>> a;
static final int INF = 987654321;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int TC = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (TC-- > 0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
dist = new int[N + 1];
a = new ArrayList<>();
for (int i = 0; i <= N; i++) {
a.add(new ArrayList<>());
}
for (int i = 0; i < M + W; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
if (i < M) {
a.get(u).add(new Road(v, c));
a.get(v).add(new Road(u, c));
} else {
a.get(u).add(new Road(v, -c));
}
}
sb.append(bellmanFord() ? "YES\n" : "NO\n");
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
public static boolean bellmanFord() {
Arrays.fill(dist, INF);
dist[1] = 0;
boolean update = false;
for (int i = 1; i < N; i++) {
update = false;
for (int j = 1; j <= N; j++) {
for (Road road : a.get(j)) {
if (dist[road.end] > dist[j] + road.weight) {
dist[road.end] = dist[j] + road.weight;
update = true;
}
}
}
if (!update) {
break;
}
}
if (update) {
for (int i = 1; i <= N; i++) {
for (Road road : a.get(i)) {
if (dist[road.end] > dist[i] + road.weight) {
return true;
}
}
}
}
return false;
}
static class Road {
int end;
int weight;
Road(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
}복잡도
- 시간: O(TC * N * (M + W))
- 공간: O(N + M + W)