11657번 - 타임머신

1️⃣ Bellman-Ford 알고리즘

 

✏️ 풀이 과정

벨만-포드 알고리즘을 구현하면 끝나는 문제입니다. 주의할 점은 음수 가중치가 있는 부분에서 사이클이 발생할 경우 가중치가 계속 낮아지는 것이 가능하다는 것입니다.(돌았을 때 마진이 -인 사이클이 있으면 사이클 입구 지점이 업데이트되고 또 같은 경로로 업데이트하며 사이클을 돌고...가 무한으로 반복됩니다.) 이를 판별하는 방법은 for문을 N번 실행해서(일직선 연결을 가정한 N-1이 가능한 최대 업데이트 횟수인데 N번 업데이트되었다는 것은 무한 업데이트를 만드는 사이클이 존재함을 의미합니다.)

 

이 알고리즘의 효율성을 높이는 방법이 있는데 바로 업데이트 여부를 체크함으로써 N-1번의 실행을 다 완료하지 않고도 업데이트가 한 번도 되지 않았을 경우 종료하는 것입니다.(한 번의 반복마다 모든 간선을 체크하는 것이기 때문에 한 번 일어나지 않으면 앞으로도 업데이트가 되지 않습니다.)

 

구현할 때 dist 배열의 경우 반드시 long으로 선언해야 합니다. 10000 * N = 5000000까지만 늘어날 수 있다고 생각하기 쉬운데 사이클이 존재할 경우 업데이트가 매번 일어나는 것이 가능해져 음수 방향으로 for문 1회마다 -10000 * 6000만큼 줄어들게 됩니다. 따라서 약 -10000 * 500 * 6000 = -30000000000까지 int 범위를 초과해 언더플로우가 일어날 수 있기 때문에 long으로 선언해야만 이를 방지할 수 있습니다.

 

⏱ 시간 복잡도

벨만-포드 알고리즘은 M개의 간선을 N-1번(사이클을 체크하려면 N번) 순회하기 때문에 시간 복잡도는 O(N*M)입니다. N이 500까지, M이 6000까지이므로 3000000을 조금 상회하는 정도의 계산량을 예측할 수 있습니다. 벨만-포드는 모든 간선을 체크하여 비효율적이기 때문에 이를 개선한 SPFA알고리즘을 사용하면 좀 더 빠르게 문제를 해결할 수 있습니다.

 

💻 코드

Java

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

public class Main{
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] Edges = new int[M][3];
		long[] dist = new long[N+1];
		int INF = 999999999;
		for(int i=2;i<=N;i++) {
			dist[i] = INF;
		}
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			Edges[i][0] = Integer.parseInt(st.nextToken());
			Edges[i][1] = Integer.parseInt(st.nextToken());
			Edges[i][2] = Integer.parseInt(st.nextToken());
		}
		boolean update;
		for(int i=0;i<N;i++) {
			update = false;
			for(int j=0;j<M;j++) {
				if(dist[Edges[j][0]] != INF && dist[Edges[j][0]] + Edges[j][2] < dist[Edges[j][1]]) {
					update = true;
					dist[Edges[j][1]] = dist[Edges[j][0]] + Edges[j][2];
					if(i == N-1) {
						System.out.println(-1);
						System.exit(0);
					}
				}
			}
			if(!update) {
				break;
			}
		}
		for(int i=2;i<=N;i++) {
			sb.append(dist[i] == INF ? -1 : dist[i]);
			sb.append("\n");
		}
		System.out.print(sb);
		br.close();
	}
}