https://www.acmicpc.net/problem/11657
문제 요약
N개에 도시에, 두 도시를 잇는 버스 M개가 있다.
버스의 정보는 시작도시, 도착도시, 걸리는 시간 순으로 주어진다.
버스의 걸리는 시간이 양수 뿐만 아니라 0 또는 음수도 가능하다.
이때 1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간을 구하여라.
시간을 무한히 되돌릴 수 있는 경우라면 첫 줄에 -1을 출력하고 끝낸다.
만약 해당 도시로 가능 경로가 없다면 시간 대신 -1을 출력한다.
도시의 개수 N은 최대 500이다.
버스 노선의 개수 M은 최대 6000이다.
버스 소요 시간 C는 최소 -1만, 최대 1만이다.
문제 접근
이 문제의 도시를 정점, 버스를 간선으로 치환한 그래프로 생각하면 결국 시작 정점에서 다른 정점까지의 최단 거리를 구하는 문제임을 알 수 있다.
어떤 알고리즘을 사용할까?
이러한 경우에는 보통 다익스트라 알고리즘을 사용하여 문제를 해결할 수 있는데, 여기서는 이를 활용하지 못한다. 왜냐하면 간선의 가중치가 음수인 경우가 존재할 수 있기 때문이다.
간선의 가중치가 음수일 때 다익스트라 알고리즘을 사용하지 못하는 이유는, 간선의 가중치가 음수라면 다시 방문했을 때의 비용이 처음 방문했을 때보다 더 작을 수 있기 때문이다. 다익스트라에서는 방문 여부를 기록하여 한 번 방문한 정점에 다시 방문하지 않기 때문에 이를 고려하지 못하게 된다.
따라서 한 정점에서 다른 정점까지의 최단 거리를 얻을 수 있는 다른 알고리즘인 벨만 포드 알고리즘을 사용해야 한다.
벨만 포드 알고리즘은 시간복잡도가 O(VE)라서 다익스트라 알고리즘에 비해 더 오래 걸리지만, 간선의 가중치가 음수인 경우에도 활용할 수 있다는 특징이 있다.
벨만 포드 알고리즘은 어떻게 동작할까?
벨만 포드 알고리즘의 아이디어는 모든 간선을 반복적으로 훑으면서 거리를 갱신한다는 것이다.
N개의 정점으로 구성된 그래프에서, 시작 정점에서 출발하여 다른 정점에 최단 거리로 도달하기 위해 거치는 간선의 개수는 아무리 많아도 N-1개를 넘을 수가 없다.
왜냐하면 최악의 경우인 1자로 연결된 그래프를 생각해도, N-1개의 간선을 거치면 도달할 수 있기 때문이다. 따라서 특정 정점에 도달하지 못하는 경우도 함께 판단된다.
벨만 포드 알고리즘을 사용하면 간선을 1개 사용할 때부터 간선을 N-1개 사용할 때까지의 최단 거리를 순서대로 찾게 된다고 생각하면 된다.
이때, 마지막으로 한 번 더 훑어서 갱신되는 최단 거리가 있는지 확인하여 음의 사이클이 존재하는지 판단할 수 있다.
앞서 N-1개의 간선을 확인하면 모든 정점에 대한 최단 거리를 얻을 수 있다고 했는데, 음의 사이클이 존재하면 이 경우에 최단 거리가 갱신되기 때문이다.
풀이
기본적인 아이디어는 다음과 같다.
- 입력을 받아 그래프를 구성한다.
- 벨만 포드 알고리즘을 기반으로 간선을 N-1번 훑어 최단 거리를 얻고, 마지막으로 한 번 더 훑어 음의 사이클이 존재하는지 확인한다.
이 문제에서 유의할 점은 거리를 long으로 나타내어야 한다는 것, 그리고 벨만 포드에서 방문한 적이 있는 정점의 간선만 훑어야 한다는 것이다.
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static long INF = 1000000000000L;
public static void main(String[] args) throws IOException {
int N, M;
ArrayList<int[]>[] graph;
long[] distance;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 입력 받기
StringTokenizer st1 = new StringTokenizer(br.readLine());
N = Integer.parseInt(st1.nextToken());
M = Integer.parseInt(st1.nextToken());
graph = new ArrayList[N+1];
distance = new long[N+1];
for (int i = 0; i < N+1; i++) {
graph[i] = new ArrayList<>();
distance[i] = INF;
}
for (int i = 0; i < M; i++) {
StringTokenizer stM = new StringTokenizer(br.readLine());
int A = Integer.parseInt(stM.nextToken());
int B = Integer.parseInt(stM.nextToken());
int C = Integer.parseInt(stM.nextToken());
int[] target = new int[] {B, C}; // {도착 도시, 걸리는 시간}
graph[A].add(target);
}
// 벨만 포드 알고리즘을 이용해 문제 해결하기
// N-1번 돌아서 최단 거리를 얻고, N번째에서 갱신되는 값이 있다면 음의 사이클이 존재함.
distance[1] = 0;
boolean negCycle = false;
for (int i = 0; i < N; i++) {
// 각 도시의 출발 버스 훑기
// 이렇게 적으면 같은 루프에서 갱신된 것에도 영향을 받는데, 어차피 별 상관 없을 것 같다.
// 버스 정보를 ArrayList가 아니라 그냥 2차원 배열로 하면 for문이 조금 더 간단해지긴 한다.
for (int j = 1; j < N+1; j++) {
for (int[] next : graph[j]) {
if (distance[next[0]] > distance[j]+next[1] && distance[j] != INF) {
distance[next[0]] = distance[j]+next[1];
if (i == N-1) negCycle = true;
}
}
}
}
// 결과 출력
if (negCycle) System.out.println(-1);
else {
for (int i = 2; i < N+1; i++) {
if (distance[i] == INF) sb.append(-1+"\n");
else sb.append(distance[i]+"\n");
}
System.out.println(sb);
}
}
}회고
틀렸던 이유 1
거리가 int 범위를 넘을 수 있다는 점을 알지 못했다.
문제 상황을 보면 간선 가중치의 절대값이 최대 1만이고, 정점이 최대 500이므로 거리는 최대 500만의 값을 가질 것이라고 생각했다.
그러나 이 문제에서는 하나의 반복문 내에서 갱신된 값이 같은 반복문의 다른 값이 갱신되는 데 사용될 수 있다.
따라서 실제로는 간선의 개수만큼 더 곱해질 수 있기 때문에 long을 사용해야 한다.
틀렸던 이유 2
벨만 포드 알고리즘의 아이디어에서 모든 간선을 정점의 수만큼 훑는다고 했지만, 이미 방문했던 정점의 간선만을 훑어야 한다.
왜냐하면 이렇게 하지 않았을 때, 시작점에서 방문하지 못하는 곳에서 발생하는 음의 사이클이 잘못된 결과를 얻게 하기 때문이다.
