문제 설명
N개의 노드가 있고, M개의 무방향 간선이 있다. 추가로 W개의 방향성 음수간선(문제에선 이걸 웜홀이라고 함)이 존재한다. 이때, 임의의 한 점에서 출발해서 순회하고 다시 돌아왔더니 오히려 시간이 뒤로 가는 경우가 있는가?
접근
거치는 간선의 가중치 합 < 거치는 간선에 있는 웜홀의 가중치합(의 절댓값)
인 경우에 문제에서 원하는 상황이 발생한다.
즉, 한바퀴를 돌았더니 그 합이 음수더라.. 아 음의 순환 사이클이 있나 궁금한거구나.
N은 최대 500개 M은 최대 2500개, W는 최대 500개임. 그리고 사실 이 문제를 풀때, 벨만 포드 알고리즘을 들어보기만 하고 정확히 뭔지 모르는 상태여서 알고 있는 플로이드 워샬을 사용해서 풀었다. 플로이드 워샬의 시간복잡도를 생각해보면, 2초안에는 충분히 풀수 있었다. i->i노드로 가는 값이 음수인지만 판단해주면 정답을 구할 수 있다.
플로이드 워샬을 사용한 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
String[] result = new String[T];
Arrays.fill(result, "NO");
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());
int[][] graph = new int[N + 1][N + 1];
for (int i = 1; i < N + 1; i++) {
Arrays.fill(graph[i], 100000000);
}
for (int i = 1; i < N + 1; i++) graph[i][i] = 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 cost = Integer.parseInt(st.nextToken());
graph[s][e] = Math.min(graph[s][e], cost);
graph[e][s] = Math.min(graph[e][s], cost);
}
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 cost = Integer.parseInt(st.nextToken());
graph[s][e] = Math.min(graph[s][e], -cost);
}
for (int k = 1; k < N + 1; k++) {
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < N + 1; j++) {
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
for (int i = 1; i < N + 1; i++) {
if (graph[i][i] < 0) {
result[t] = "YES";
break;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < T; i++) {
sb.append(result[i]).append("\n");
}
System.out.print(sb);
}
}
시간이 다른사람들 풀이보다 오래걸린다.
뭔가 잘못됐음을 직감하고 문제의 유형을 보았다. 벨만 포드라는 말이 적혀있었다. 이참에 공부를 해보았고 정리를 아래에 해놨다. 벨만 포드 알고리즘으로 해결한 코드는 아래와 같다.
import java.util.*;
import java.io.*;
public class Main {
static class Edge {
final int s;
final int e;
final int cost;
Edge(int s, int e, int cost) {
this.s = s;
this.e = e;
this.cost = cost;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
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());
ArrayList<Edge> edges = new ArrayList<>();
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 cost = Integer.parseInt(st.nextToken());
edges.add(new Edge(s, e, cost));
edges.add(new Edge(e, s, cost));
}
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 cost = Integer.parseInt(st.nextToken());
edges.add(new Edge(s, e, -cost));
}
int INF = 500_0001;
int[] table = new int[N + 1];
Arrays.fill(table, INF);
table[1] = 0;
// 노드의 갯수 - 1 개 만큼 수행
for (int i = 0; i < N - 1; i++) {
for (Edge edge : edges) {
if (table[edge.e] > table[edge.s] + edge.cost) {
table[edge.e] = table[edge.s] + edge.cost;
}
}
}
// 정상적인 음의순환이 없다면, 더이상 갱신되면 안됨.
boolean hasNegativeCycle = false;
for (Edge edge : edges) {
if (table[edge.e] > table[edge.s] + edge.cost) {
hasNegativeCycle = true;
break;
}
}
if (hasNegativeCycle) {
sb.append("YES").append("\n");
} else {
sb.append("NO").append("\n");
}
}
System.out.print(sb);
}
}
주의할 점으로, 여기서 edge들간 연결되어있다는 보장이 문제에 없었다. 그래서, 순회할때 벨만-포드 알고리즘의 if문 조건 두 개 중 하나(table[edge.e]!=INF)를 제거해줘야한다(이 부분은 다른사람의 풀이를 참조했다).
위 조건식이 들어가게 되면, 우리가 시작점으로 table값을 0으로 준 노드와 연결되지 않은 그래프들은 영원히 갱신될 수 없어서, 그 안에 사이클이 존재하면 찾을 수 없다. 벨만-포드는 원래 한 시작 노드에서 다른 모든 노드까지의 최단거리를 찾는것이 목표인 알고리즘에 주의하자.
또한, 벨만-포드는 모든 간선을 노드갯수만큼 순회한다는 조건에서 알 수 있듯이 노드에 대한 정보보다 간선이 더 중요한 기준이라서 class Node가 아니라 class Edge를 만들었다.
그냥 노드갯수만큼 반복하면서, 모든 엣지를 순회하고 계속 table을 갱신시켜 나가면 된다.
배운것
다익스트라는 음수간선있으면 아예 안된다.
1노드에서 다른 모든 노드까지의 최단거리 구하는게 목적.
왜? dp + 그리디의 성격이 있는 다익스트라는 음수 간선이 있는 그래프에서는 다익스트라의 그리디가 적용이 안되기 때문임.시간복잡도 O(ElogV) -> 최소힙 적용 기준
플로이드 워샬은 음수간선있으면 안된다. 단,, a->b라는 경로 사이에 음의 순환이 있는지는 판단가능함.
모든 노드에서 다른 모드 노드까지의 최단거리 구하는게 목적.
dp를 적용해서, 그냥 for문 k,i,j 세개 연속으로 적용해서 구한다. 음수 간선이 있다면 아쉽게도 최단 거리의 답을 온전히 찾을 수는 없지만, a에서b의 경로 사이에 음의 순환이 있는지는 판단 가능하다.
시간 복잡도 O(V^3)
벨만 포드 알고리즘은 음의 간선이 있어도 된다.
한 노드에서 다른 모든 노드로의 최단거리를 찾아내며, 음의 간선이 있어도 온전히 답을 찾을 수 있다. 단, 음의 순환이 존재하는 경우에는 답을 못찾으며(사실 음의 순환이 있는 순간, 비용을 줄이려면 얼마든지 줄일 수 있어서 못찾는게 당연하다), 대신 그 사이에 음의순환이 있는지 쉽게 판단 가능하다.
다익스트라는 이미 방문처리된 요소와 이어진 간선을 무시하지만, 벨만 포드는 이 간선이 음의 가능성일 수 있어서 이미 방문한 노드에 대해 새로운 최단거리를 찾을 수도 있다고 생각하고, 모든 간선을 확인한다. 이런 행위를 노드의 갯수만큼 계속해서 간선들을 모두 확인하기 때문에 시간복잡도는 O(VE)다.
즉, V개의 노드에 대해 모든 순환을 돌아야 하는데 마지막 방문한 V번째노드에 대해서도 최단거리 갱신이 이루어지려 한다는 것은 그 그래프 안에 음의 순환이 존재한다는 것이다.
정상적인 경우(음의 순환이 없는)라면, V-1번째 노드까지 봤을때 더이상 갱신되면 안된다.
