[BOJ] 백준 11657번 타임머신 (Java)

#11657 타임머신

난이도 : 골드 4

유형 : 그래프 탐색 / 벨만-포드 알고리즘

11657번: 타임머신

▸ 문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

▸ 출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

문제 풀이  

최단 경로 알고리즘은 모든 간선이 양수인 경우와 음수 간선이 있는 경우로 나눌 수 있다. 

• 모든 간선이 있는 경우 - 다익스트라 (한 정점 → 모든 정점), 플로이드-와샬(모든 정점 → 모든 정점)
• 음수 간선이 있는 경우 - 벨만-포드 

해당 문제는 1번 도시에서 출발해 다른 모든 정점의 최단 거리를 구하는 문제이다.

그리고 타임머신이라는 내용으로 간선에 음수를 포함시켰으므로 벨만-포드 알고리즘으로 풀이를 할 것이다.

 

📚 조건

• 도시의 개수 N ( 1 <= N <= 500)
• 버스 노선의 개수 M ( 1<= M <= 6,000)
• 음수 간선 순환이 존재하는 그래프이면 -1을 출력하고 종료한다.
• 음수 간선 순환이 존재하지 않으면 1번 도시에서 출발해 2~N번 도시로 가는 가장 빠른 시간 순서대로 출력한다. 해당 도시로 경로가 없으면 -1을 출력한다.

 

동작 과정

1. 최단 거리 테이블을 초기화 시킨다.
2. 1번 도시를 출발 노드로 설정하고 N-1번의 반복을 돌려 벨만포드 알고리즘을 이용하여 각 도시로 가는 최단 거리를 갱신한다.
3. 마지막으로 N번쩨 탐색에서 음수 순환의 존재 여부를 파악한다.
   1. 값이 작아진 경로가 있다면 해당 경로는 음수 간선이 포함된 싸이클로 음수 무한대로 수렴하기 때문에 경로가 없다고 간주한다.
   2. 음수 순환이 없으면, 최단 거리 테이블을 조회하여 초기값이 갱신되지 않은 도시는 경로가 없으므로 -1, 그 외에는 최단거리를 출력해준다.

 

풀이 코드 

최대 경로의 길이는 N-1이다. 해당 그래프는 음수 간선이 들어있기 때문에 최단 거리가 매번번 갱신 될 수 있기 때문에 N-1번의 반복을 돌려주어 매번 모든 간선을 전부 확인해줘야 한다. 그리고 최대 경로길이를 초과한 N번째 탐색에서 값이 갱신된다는 소리는 음수 싸이클이 존재한다는 것으로 간주할 수 있다.

import java.io.*;
import java.util.StringTokenizer;

class Bus{
	int u;
	int v;
	int val;
	public Bus(int u,int v, int val) {
		this.u = u;
		this.v = v;
		this.val = val;
	}
}
public class Main {
	static int n,m;
	static Bus[] e;
	static long[] dist;
	static int INF = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		e = new Bus[m];
		dist = new long[n+1];
		// 최단 거리 테이블 초기화
		for(int i=1; i<n+1; i++) {
			dist[i] = INF;
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			e[i] = new Bus(u,v,val);
		}
		
		if(bellmanford(1)) { // 음수 순환 존재하면 -1 출력 
			System.out.println(-1);
		}
		else {
			// 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단거리 출력 
			for(int i=2; i<n+1; i++) {
				if(dist[i] == INF) {// 도달할 수 없으면 -1 
					System.out.println("-1");
				}
				else { // 최단 거리 출력 
					System.out.println(dist[i]);
				}
			}
		}
		
	}
	static boolean bellmanford(int start){
		dist[start] = 0;
		
		// n번 반복 
		for(int i=1; i<n+1; i++) {
			// 매 반복마다 모든 간선을 확인 
			for(int j=0; j<m; j++) {
				int cur = e[j].u;
				int next = e[j].v;
				int cost = e[j].val;
						
				if(dist[cur] == INF) continue;
				// 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 짧은 경우 
				if(dist[next] > (dist[cur] + cost)) {
					dist[next] = dist[cur] + cost;
							
					// n번째 라운드에서 값이 갱신된다면 음수 순환 존재 
					if (i == n) {
						return true;
					}
				}
			}
		}
		return false;
	}
	
	
}