[BOJ] 11657 타임머신 Java 풀이

 

BOJ 11657 타임머신

 

이전 1753번 최단경로 문제와 같이 최단경로 유형의 문제다. 다만 이번에는 버스 노선이 edge인데 음수 범위를 포함하기 때문에, 벨만 포드 알고리즘을 사용해 최단경로를 구해주어야 한다.

이번 문제에서 유의해야 할 점은 최단 경로를 나타내는 dist 배열을 int가 아닌 long으로 설정해줘야 한다는 점이다. 
이 점을 캐치하지 못하고 출력초과 결과를 받아 오래 헤맸다. (이 문제에서 출력초과는 사실상 음수사이클 판정을 하지 못한 것)

간선 weight의 범위가 -10,000 < C < 10,000이고, 노드의 수가 최대 500임에도 dist 배열을 long으로 설정해줘야 하는 이유는 경로의 weight를 계산하는 과정에서 음의 사이클이 존재하는 경우 알고리즘 내부 반복문을 한 번 돌 때마다 최악의 경우 -6,000만으로 형성되는데, 이를 499번 반복하기 때문이다.

500 * 6000 * (-10000) < Integer.Min_VALUE 

이러한 경우는 꼭 이 문제만이 아니라 음수사이클이 존재하는 경우 항상 발생할 수 있으니 벨만포드 알고리즘을 적용할 때는 이 점을 유의해야 하겠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static ArrayList<Node>[] adj;
	static long dist[];
	static boolean has_minus_cycle;
	static int INF = 6000000;
	static int Start = 1;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// initialize
		adj = new ArrayList[N + 1];
		dist = new long[N + 1];
		for(int i = 1; i <= N; i++) {
			adj[i] = new ArrayList<>();
			dist[i] = INF;
		}
		
		// input processing
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			adj[a].add(new Node(b, c));
		}
		
		bell(Start);
		
		// output processing
		if(has_minus_cycle) {
			System.out.println(-1);
		}else {
			for(int i = 1; i <= N; i++) {
				if(i != Start) {
					if(dist[i] == INF) System.out.println(-1);
					else System.out.println(dist[i]);
				}
			}
		}
	} // end of main
	
	private static void bell(int start) {
		dist[start] = 0;
		
		for(int i = 0; i < N - 1; i++) {	// 최대 방문할 수 있는 노드의 개수만큼 
			for(int j = 1; j <= N; j++) {	// j점 주변에 있는 점들을 업데이트 할 수 있는지 확인
				for(int k =0; k < adj[j].size(); k++) {		// j점에서 출발할 수 있는 버스 노선
					Node next = adj[j].get(k);
					
					// 현재 버스 노선이 기존 최단 경로를 갱신할 수 있다면
					if(dist[j] + next.weight < dist[next.dest] && dist[j] != INF) {
						// 갱신
						dist[next.dest] = dist[j] + next.weight;
					}
				}
			}
		}
		
		// 최단 경로를 구했는데, 한 번 더 갱신이 일어난다면 minus_cycle 존재
		for(int j = 1; j <= N; j++) {	// j점 주변에 있는 점들을 업데이트 할 수 있는지 확인
			for(int k =0; k < adj[j].size(); k++) {		// j점에서 출발할 수 있는 버스 노선
				Node next = adj[j].get(k);
				
				// 현재 버스 노선이 기존 최단 경로를 갱신할 수 있다면
				if(dist[j] + next.weight < dist[next.dest] && dist[j] != INF) {
					// 갱신
					has_minus_cycle = true;
					return;
				}
			}
		}
		
		
	}
}
class Node{
	int dest, weight;

	public Node(int dest, int weight) {
		this.dest = dest;
		this.weight = weight;
	}
	@Override
	public String toString() {
		return "Node [dest=" + dest + ", weight=" + weight + "]";
	}
}