[알고리즘] 백준 11657번: 타임머신 (C++), 벨만 포드

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

11657번: 타임머신

[벨만 포드 정리]

(https://yabmoons.tistory.com/365)

다음 블로그를 통해 정리했다.

 

1. 모든 간선들을 탐색하면서 간선이 잇는 출발 정점이 '한 번이라도 계산된 정점'이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트한다.

2. 1번 과정을 반복한다.

 

[한 번이라도 계산된 정점 == dist의 값이 INF가 아닌 정점]

>> '한 번이라도 계산된 정점'이어야 하는 이유는 참고한 블로그에 자세히 설명이 나와있고, 블로그에서 사용하신 그래프 사진을 함부로 들고 올 수 없어서 글로 간단하게 설명해보자.

1번을 보면 '모든 간선들을 탐색하면서'라고 나와있다. 그렇다면 벨만 포드 알고리즘은 시작 노드를 중심으로 두지 않고, 간선을 중심으로 최소 비용 경로들을 업데이트하겠다는 소리다.그렇다면 발생하는 문제는 '방문하지 않은 노드', 즉 시작 노드로부터 아예 갈 수 조차 없는 노드를 포함한 간선이 업데이트될 수도 있다는 얘기다.>> 그래서 이 문제는 다음과 같이 해결한다. >> '한 번이라도 계산된 정점'

if (dist[from] == INF) continue;

시작 노드는 dist값을 0으로 초기화시키기 때문에 상관없다.

 

[음수 사이클 (서론)]

벨만 포드 알고리즘은 최소 비용을 구할 수 있는 알고리즘이지만 한 노드로부터 최소 비용을 구하는 점이 다익스트라와 닮아있다. 하지만, 시간 복잡도 측면에서 다익스트라(O(E*logV))가 더 빠르다. (벨만 포드 = O(V * E))

그리고, 음수 가중치를 처리할 수 있다는 점에서 플로이드 와샬이 떠오르지만 그럼에도 불구하고, 벨만 포드를 배워야 하는 이유는 '음수 사이클' 때문인 거 같다.

 

음수 사이클에 대해 들어가기 전에 벨만 포드는 어떻게 생겼는지 알아보자.

[벨만 포드 구현]

1) 최소 비용을 모두 업데이트하려면 최소 N - 1번의 반복이 필요하다.

왜냐하면 1의 dist값이 0이라면 다른 노드들의 dist값은 현재 INF다. 1을 제외한 노드들은 dist값이 INF, 즉 '한 번이라도 계산된 정점'이 아니라서 무시한다. 한번 더 경로 값들을 업데이트해주었을 때는 1과 인접한 노드들의 dist값이 갱신이 된다. 즉, 간선 값들을 여러 번 업데이트해주어야 최소 비용을 전부 업데이트할 수 있다는 말이 된다.

 

그런데 N - 1번인 이유는 1자형 그래프를 생각해보면 된다. ((0-0-0-0-0-0) 이런 식으로 생긴 그래프)

이 그래프의 경우가 업데이트를 총 N - 1번 해주어야 모든 최소 비용 경로 값들이 갱신이 되는 그래프다.

N - 1 이내로 비용 값들은 전부 업데이트된다는 뜻!

 

2) 엣지의 개수만큼 모든 엣지들을 업데이트한다.

단, 엣지의 시작 노드가 INF값일 때는 continue 시킨다. ('한 번이라도 계산된 정점'의 이유)

void bellmanFord() {
	dist[1] = 0;

	for (int i = 1; i <= n - 1; i++) {
		for (int j = 0; j < edge.size(); j++) {
			int from = edge[j].first.first;
			int to = edge[j].first.second;
			int cost = edge[j].second;

			if (dist[from] == INF) continue;
			if (dist[from] + cost < dist[to]) {
				dist[to] = dist[from] + cost;
			}
		}
	}
	return;
}

 

[음수 사이클 (본론)]

음수 사이클 == 최소 비용을 업데이트할수록 계속 어떠한 정점의 관한 최소 비용이 변하는 것

그렇다면 어떻게 음수 사이클 유무를 판단할 수 있나?

N - 1번 최소 비용을 업데이트 해준 상태에서 한 번 더 업데이트를 해줬을 때, 변화가 생긴다면 이는 음수 사이클을 가지고 있다고 볼 수 있다.

 

[궁금한 점]

Q: 음수 사이클이 존재하는 그래프라면 N - 1번 업데이트했을 때 그것은 최소 경로 비용을 구했다고 할 수 있는가?

 

[문제]

음수 사이클을 담는 자료형의 값이 int보다 범위를 더 크게 가질 수 있어서 long long으로 선언해야 한다고 한다.

아직 이유를 파악 못 했으나 벨만 포드에 대해 아직 궁금한 게 많아서 그때 모조리 파헤쳐 볼 생각이다.

(long long인 이유 https://www.acmicpc.net/board/view/55270)

+ int 자료형의 크기로 최솟값이 갱신이 되어야 음수 사이클의 유무를 파악할 수 있는데 참고한 링크에서 설명되어있는 케이스가 언더플로우 현상 때문에 최솟값이 갱신되지 않아서 갱신할 수 있게끔 자료형을 더 크게 잡아주어야 된다고 한다.

#include <iostream>
#include <vector>
#define MAX 500 + 1
#define INF 987654321
#define pii pair<int, int>
#define ll long long
using namespace std;

int graph[MAX][MAX];
ll dist[MAX];
vector<pair<pii, int>> edge;
int n, m;

bool bellmanFord() {
	dist[1] = 0;

	
	for (int i = 1; i <= n - 1; i++) {
		for (int j = 0; j < edge.size(); j++) {
			int from = edge[j].first.first;
			int to = edge[j].first.second;
			int cost = edge[j].second;

			if (dist[from] == INF) continue;
			if (dist[from] + cost < dist[to]) {
				dist[to] = dist[from] + cost;
			}
		}
	}

	for (int j = 0; j < edge.size(); j++) {
		int from = edge[j].first.first;
		int to = edge[j].first.second;
		int cost = edge[j].second;

		if (dist[from] == INF) continue;
		if (dist[from] + cost < dist[to]) {
			dist[to] = dist[from] + cost;
			return 1; // 음수 사이클
		}
	}

	return 0;
}

int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back({ {a, b}, c });
	}

	if (bellmanFord()) {
		cout << -1;
	}
	else {
		for (int i = 2; i <= n; i++) {
			if (dist[i] == INF) cout << -1 << '\n';
			else cout << dist[i] << '\n';
		}
	}

	return 0;
}