BOJ 11657 타임머신

 

11657번: 타임머신

해당 문제는 최단경로를 구하는 문제이지만 '음수 경로'를 허용하고 있으므로 다익스트라가 아니라 벨만 포드를 사용해야 한다.

다익스트라는 그리디 방법이기 때문에 음수 경로가 있을 때 최단 경로를 선택하지 않을 수 있다. 

하지만 벨만포드 알고리즘은 V-1번의 relaxation 과정을 통해 모든 엣지를 돌며 각각 노드의 모든 indegree로부터의 최저 가중치를 계산하게 되므로, 음수 경로를 허용한다.

하지만 벨만포드 역시 '음수 사이클'이 존재하는 경우는 계속해서 가중치가 작아져 결국 최단경로가 존재하지 않게된다. 

이러한 벨만포드의 특징을 살려서 타임머신 문제는 '음수 사이클'이 있는 경우는 따로 처리를 해주어야 한다.

 

* 해당 문제에서 주의해야 할 점

가장 많이 나는 오답중에 하나인 '출력초과'는 음수 사이클인경우 -1을 출력해주어야 하는데 , 2~N 까지의 경로를 출력해준 경우이다. 

경로를 저장해주는 배열에서 오버플로우가 발생하면 당연히 음수사이클 판명을 제대로 못해주어서 출력초과가 난다.  따라서 이 오버플로우를 꼭 방지해주어야 한다 

 

일단 벨만포드의 몇가지 중요한 점을 살펴보자면

0) relaxation 

벨만포드에서는 V-1번의 relaxation을 통해서 해당 경로까지의 최적해를 구한다. 아래 relaxation 코드를 보면 더 이해가 쉽게 될 것이다.

for(int i = 1; i<=N-1; i++) { // 정점 수 -1 
		for(int j=0;j<M; j++) { //간선수 M 
			int u =edge[j].src; //from
			int v=edge[j].dest; //to 
			int w=edge[j].weight; //가중치
			//dist[u]가 구해졌음 && dist[v]가 dist[u] + v의 가중치보다 크면 
			if(dist[u]!=INF && dist[v] > dist[u]+w) {
				dist[v] = dist[u]+w; //갱신 
			}
		}
	} 

여기서 inner loop는 모든 간선을 살펴보며 , 간선의 도착점(v)과 출발점(u)이 있을 때 출발점이 구해졌다면 (출발점까지의 최단경로+ 현재 간선의 가중치 ) 와 (도착점까지의 최단경로) 중에 작은 것을 택해서 다시 (도착점 까지의 최단경로)에 저장하게 된다.

 

 

1) relaxation은 왜 V-1 번 해야하는가 

정점의 개수가 V 개이고 사이클이 없는 경우 간선의 개수는 V-1 이어야 하기 때문이다 . 간선의 개수가 V-1이 넘는다면 사이클을 가지고 있음을 뜻한다.

따라서 ,음수 사이클이 있는지 판명하기 위해서는 relaxation이 V-1번 끝난후 다시 한번 돌려줘서 값이 변하는지 확인해야 한다. 여기서 값이 변하면 음수 사이클이 있다는 것이다.

 

2)  벨만포드는 결국 다이나믹 프로그래밍이다. 

일단 문제에서도 출발점이 첫번째 노드이기 때문에, 우리는 각각의 relaxation 과정을 통해서 

(시작정점~정점 i ) 의 최단경로를 구하게 된다. 그리고 이를 바탕으로 (시작정점 ~ 정점 i+1) 의 최단 경로를 구하게 되는 것이다. 이런식으로 (시작정점~마지막 정점) 까지 구하게 된다. 

이는 결국 벨만포드 알고리즘이 최적해를 바탕으로 최적해를 구하는 다이나믹 프로그래밍임을 알 수 있다.

 

3) 벨만포드 알고리즘의 시간 복잡도

일단 위의 relxation 루프에서 극명하게 보이듯이, subproblem의 수는 V^2 개, 그리고 이 subproblem 각각의 연산은 V-1 번이 걸린다. 따라서  O (V-1 * E) 로, 여기서 E = O(V^2) 이므로 O(V^3) 이 되겠다.

 

아래는 자바 소스코드이다.

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

/* boj 11657 타임머신
 * 벨만포드 알고리즘 사용
 * 오버플로 때문에 제대로 음수 사이클 측정이 안될 수 있으므로 거리 저장 배열 타입은 long
 * */

class Graph //edge 정보 객체배열로 저장 
{
	Graph(int src, int dest ,int weight){
		this.src=src;
		this.dest=dest;
		this.weight=weight;
	}
	int src; //from
	int dest; //to 
	int weight;  //가중치 
}


public class Main {
	private static final int INF = Integer.MAX_VALUE;
	private static int N; //도시 개수 
	private static int M; //버스 노선 개수 
	private static Graph[] edge; //엣지 저장 
	private static long[] dist; //노드 1로부터 각각의 노드 까지의 최단경로 저장
   public static void main(String[] args) throws IOException{		
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   StringTokenizer stk = new StringTokenizer(br.readLine());
	   N = Integer.parseInt(stk.nextToken());
	   M = Integer.parseInt(stk.nextToken());
		dist = new long[N+1]; //초기화 
		edge = new Graph[M]; //초기화 
		for(int i=0; i<M;i++) { //간선 입력 
			stk = new StringTokenizer(br.readLine());
			int src = Integer.parseInt(stk.nextToken());
			int dest = Integer.parseInt(stk.nextToken());
			int weight = Integer.parseInt(stk.nextToken());
			edge[i]=new Graph(src,dest,weight);
		}
		Arrays.fill(dist, INF); //초기화 
		dist[1]=0; //출발 노드 초기화 
		if(bellmanFord()==false) { //음수 사이클 있음 
			System.out.println("-1");
		}
		else { //음수 사이클 없음 
			for(int i = 2; i<=N; i++) {
				if(dist[i]==INF) {
					System.out.println("-1"); //연결 되어 있지 않음 
				}
				else {
					System.out.println(dist[i]); //최단경로 출력 
				}
			}
		}
	}
	
	
	public static boolean bellmanFord() {
		for(int i = 1; i<=N-1; i++) { // 정점 수 -1 
			for(int j=0;j<M; j++) { //간선수 M 
				int u =edge[j].src; //from
				int v=edge[j].dest; //to 
				int w=edge[j].weight; //가중치
				//dist[u]가 구해졌음 && dist[v]가 dist[u] + v의 가중치보다 크면 
				if(dist[u]!=INF && dist[v] > dist[u]+w) {
					dist[v] = dist[u]+w; //갱신 
				}
			 }
			} 
		
		for(int j=0; j<M; j++) { //음수사이클 다시한번 확인 	
			int u = edge[j].src; //from
			int v= edge[j].dest; //to 
			int w = edge[j].weight; //가중치 
			if( dist[u]<INF && dist[v] > dist[u]+w) {
				return false; //값이 또 적게 변할 수 있다면 계속 변하는 음수사이클이 있다는 것. 따라서 false 리턴 
			}
		}
		return true; //음수사이클 없음 
		
	}
}

 

 

 

 

벨만포드 알고리즘 관련 자료 추천

Bellman–Ford Algorithm | DP-23 - GeeksforGeeks