[BOJ] 11657. 타임머신 - JAVA (벨만포드)

🔗 문제

https://www.acmicpc.net/problem/11657

11657번: 타임머신

 

🧩 풀이 및 코드

문제 유형 : 그래프 이론, 벨만-포드

 

풀이

벨만 포드 (BellmanFord) 알고리즘

개념

가중 유향 그래프에서 최단 경로를 구하는 알고리즘이다.

벨만 포드 알고리즘 동작 원리는 다익스트라(Dijkstra) 와 유사하다.

차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 적용할 수 있으며 시간 복잡도가 O(VE)이다. (V: 정점의 갯수, E: 간선의 갯수)

다익스트라 알고리즘에서 우선순위 큐를 이용한 방식으로 시간구현하면 시간 복잡도 O(VlogV) 이므로 벨만 포드 알고리즘보다 실행속도가 빠르다.

 

다익스트라 알고리즘의 한계

정점 A -> C 로 갈 때, 두 가지 경로가 존재한다.

① A -> B -> C

② A -> C 

① 의 비용은 7 + (-4) = 3, ② 의 비용은 5 이므로 ① 의 경로가 최단 거리 비용이다. 

하지만, 다익스트라 알고리즘에서는 정점 A 와 연결된 정점 B, C 중에서 7 > 5 이므로 C 로 가는 경로를 선택해 최단 거리 비용을 5로 확정한다.

이와 같은 오류는 다익스트라 알고리즘 구현 조건 자체가 가중치는 양의 정수이기 때문이다.

이는 벨만 포드 알고리즘을 통해 해결할 수 있다. 하지만 벨만 포드 알고리즘으로도 해결하지 못하는 경우가 있다.

그건 음의 사이클이 형성되는 경우이다. 

 

음수 가중치의 문제

음의 가중치 자체가 문제가 되는 것은 아니지만음수 가중치는 아래와 같이 음의 값이 누적되는 사이클이 형성되면 문제가 된다. 

A -> D 로 가는 최단 거리 비용을 생각해보자.비용 : 2 -> 3 -> -6 -> 3 -> -6 -> 3 -> -6 -> ... 무한히 최소 거리가 작아진다. 

그렇기 때문에 벨만 포드 알고리즘에서는 음의 값이 누적이 되는 사이클이 존재하는 경우 의미 없는 값을 반환하므로 음의 사이클이 있는지를 확인해야 한다.

 

	다익스트라	벨만-포드
음수 가중치	X	O
음수 사이클	X	X
시간 복잡도	O(mlogn)	O(mn)

 

알고리즘

① 각 정점들을 차례로 돌아 모두 탐색한다. 이때 해당 정점들과 연결된 간선들을 탐색한다. 

② int[] dist 배열에 시작점부터 각 정점까지 최단 거리 비용을 계산한다. 다른 정점은 INF 로 초기화하고 시작 정점은 0 으로 초기화한다. 

③ 기준 정점 (S) 와 도달하고자 하는 정점 (T) 라고 한다면 dist[T] >= d[S] + cost(S, T) 식이 성립할 경우 dist 를 업데이트한다. (기준 정점을 거쳐서 T에 도달하는 게 더 최단 거리 비용)

④ 위와 같은 방식을 정점과 연결된 모든 간선으로 반복하고, 이를 정점의 수만큼 반복한다.

⑤ 최종적으로 시작점부터 모든 각 정점의 최단 거리가 구해진다.

⑥ 마지막으로 음의 사이클이 없는지 확인한다. 위와 같은 모든 정점을 모두 탐색하는 과정을 한 번 더 거쳤을 때, dist 값이 변화한다면 음의 사이클이 있다는 의미이므로 해당 그래프에선 벨만 포드 알고리즘을 사용할 수 없다. (지금까지 구한 최단 거리 비용 모두 의미 없는 값! 못씀)

 

그림을 보며 동작 과정을 이해해보자.

시작점은 1이다. 그리고 각 정점들의 최단 거리를 저장하는 1차원 배열 Dist 를 정의한다.

시작 거리는 0으로 놓고 나머지 정점들은 INF 로 초기화한다.

 

시작점고 연결된 2, 3, 4, 5 정점을 탐색한다.

• Dist [2]

Dist[2] > Dist[1] + cost(1, 2) 

INF > 0 + -4 

이므로 Dist[2] 를 업데이트한다. 정점 3와 4도 마찬가지이다.

 

 

정점 2번 차례이다. 2번 정점과 연결된 간선을 탐색한다. 정점 4 밖에 없다.

• Dist [4]

Dist[4] > Dist[2] + cost (2, 4)

2 > (-4) + (-1) 

이므로 DIst[4] 가 없데이트된다. 정점 1 -> 정점 4로 갔을 땐 비용이 2 였는데 정점 2를 거쳐서 1 -> 2 -> 4 로 갔을 땐 비용이 -5 로 더 줄어든다는 의미이다.

 

나머지 3~5 에 대해서도 반복한다.

최종적으로 시작점 1 에서 다른 정점들까지의 최단 거리 비용을 계산할 수 있게 되었다.

하지만 Bellman-Ford 알고리즘에서 확인해야 할 건 음수 사이클이 있는지 확인해야 한다.

지금까지 했던 과정을 한번 더 반복하는 것이다. 음수 사이클이 없다면 V 만큼 돌아서 계산했던 값이 한 번 더 V 번 돈다고 값이 변경되지 않는다. 변경된다는 건 음수 사이클이 있다는 의미이다.

위의 알고리즘들을 코드로 나타내보자.

 

코드

class Edge {
	int u; 
	int v; 
	int cost;

	public Edge(int u, int v, int cost) {
		this.u = u;
		this.v = v;
		this.cost = cost;
	}
}

public class Main {
	static List<Edge> edgeList;
	static final int INF = 100_000_000;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        
		// 정점의 개수, 간선의 개수 
		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());

		edgeList = new ArrayList<>();

		StringTokenizer st;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());

			edgeList.add(new Edge(u, v, cost));
		}
		
        	//벨만-포드 알고리즘 수행
        	//정점의 갯수, 간선의 갯수, 시작 정점
		BellmanFord(n, m, 1);
	}
    
    
	public static boolean BellmanFord(int n, int m, int start) {
		int[] dist = new int[n + 1];
		Arrays.fill(dist, INF);
		dist[start] = 0;

		//정점의 개수만큼 반복
		for (int i = 0; i < n; i++) {
			//간선의 개수만큼 반복
			for(Edge edge : edgeList) {
				if(dist[edge.u] != INF && dist[edge.v] > dist[edge.u] + edge.cost) {
					dist[edge.v] = dist[edge.u] + edge.cost;
				}
			}
		}
		
		//음의 사이클 확인
		for(Edge edge : edgeList) {
			
			//현재 간선의 들어오는 정점에 대해 비교 -> 더 작은 값 생기면 음수 사이클 존재
			if(dist[edge.u] != INF && dist[edge.v] > dist[edge.u] + edge.cost) {
				System.out.println("음수 사이클 존재");
				return false;
			}
		}
		
		//시작점부터 각 정점까지의 최단 거리 비용 출력
		for (int i = 1; i < dist.length; i++) {
			if (dist[i] == INF)
				System.out.print("INF ");
			else
				System.out.print(dist[i] + " ");
		}
		
		return true;
	}
}

 

느낀 점

새로운 알고리즘 하나 배웠다!

 

전체 코드

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

public class Main_bj_11657_타임머신 {
	
	static class Edge {
		int u;
		int v;
		int cost;
		
		Edge(int u, int v, int cost) {
			this.u = u;
			this.v = v;
			this.cost = cost;
		}
	}
	
	static int INF = 100_000_000;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_11657.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		List<Edge> edgeList = new ArrayList<>();
		
		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());
			
			edgeList.add(new Edge(a, b, c));
		}
		
		// 벨만 포드
		long[] dist = new long[N+1];
		Arrays.fill(dist, INF);
		dist[1] = 0;
		
		// 정점의 갯수 만큼 반복
		for(int i=1; i<=N; i++) {
			
			for(Edge edge : edgeList) {
				if(dist[edge.u] != INF && dist[edge.v] > dist[edge.u] + edge.cost) {
					dist[edge.v] = dist[edge.u] + edge.cost;
				}
			}
		}
		
		boolean res = false;
		// 음의 가중치 확인
		for(int i=1; i<=N; i++) {
			
			for(Edge edge : edgeList) {
				if(dist[edge.u] != INF && dist[edge.v] > dist[edge.u] + edge.cost) {
					res = true; 
					break;
				}
			}
		}
		
		if(res) {
			System.out.println(-1);
		} else {
			StringBuilder sb = new StringBuilder();
			for(int i=2; i<=N; i++) {
				if(dist[i] >= INF) {
					sb.append(-1).append("\n");
				}
				else sb.append(dist[i]).append("\n");
			}
			
			System.out.println(sb.toString());
		}
		
		br.close();
		
	}

}

 

 

---

Reference

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘/Java] 벨만-포드(Bellman-Ford) 알고리즘

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘/Java] 벨만-포드(Bellman-Ford) 알고리즘

https://developer-davii.tistory.com/89

[Algorithm] 벨만포드(BellmanFord) 알고리즘 JAVA