[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

우선 이 문제를 풀기위해서는 벨만-포드 알고리즘을 이해해야한다.

벨만-포드

1. 단일시작점 알고리즘 (출발 노드가 고정)
2. 최단 경로 알고리즘
3. 음수 간선 가능
4. 음수 사이클 확인 가능

쓱 보면 다익스트라와 비슷해보인다.(https://guccin.tistory.com/112?category=977502)
그러나 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선에 대해서 최단거리를 알아낼수 있다.
또한 다익스트라는 우선순위 큐를 활용하여 최단 경로를 구하는데에 반해 벨만-포드는 매번 모든 간선을 전부 확인하며 최단거리를 알아내기 때문에 다익스트라보다 시간복잡도가 크다. 다익스트라 O(|E||log|V|), 벨만-포드 O(|E||V|)

[c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 )

 

벨만-포드 진행과정

1. 최단거리 테이블 초기화
2. 출발노드 설정
3. V번 루프를 돈다.
4. 중간노드 루프를 돈다.
5. 중간노드의 간선들을 확인하여 upper 배열을 완화시킨다.
6. V번째 루프에서 음수사이클이 존재하는지 판단한다.(완화가 일어났는지 확인)

그럼 대강 알았으니 더 공부하기 위해서는 동빈나님의 영상을 참고하면 좋을것 같다.(https://www.youtube.com/watch?v=Ppimbaxm8d8)

이제 문제에 접근해보자

문제에서 주어지는 것은 그래프의 노드 개수와 간선 정보이다. 여기서 주요 포인트는 아래와 같다.

* 양수가 아닌 음수 가중치가 존재한다.
* 출발지가 1로 고정되기 때문에 단일 시작점 알고리즘이다.
* 시간을 무한히 오래전으로 되돌릴수 있다는 의미는 음수 사이클이 존재할 수 있다는 소리다.

그렇다면 결론적으로 다익스트라를 사용할 수 없다. 따라서 음수 가중치의 최단 경로를 구할 수 있고 음수 사이클까지 확인 가능한 벨만-포드 알고리즘을 사용해야 한다.

그럼 이를 토대로 코드를 짜면된다.
이때 주의해야 할 것은 가중치의 최댓값이 int가 아닌 long long이어야 한다는점.
또한, 언더플로우와 오버플로우를 막기 위해 중간노드의 최단거리가 이미 INF라면 연산을 생략해준다는 점이다.

#include<iostream>
#include<algorithm>
#include<vector>

#define MAX_N 501
#define INF 200000000000000000
using namespace std;
int N, M;
vector<pair<int, int>> adj[MAX_N];

void bellman() {
	// upper를 INF로 초기화, src 초기화
	vector<long long> upper(N + 1, INF);
	upper[1] = 0;//1에서 1로 가는 경우 비용 0

	// 완화 체크
	int updated = 0;
	// v만큼 반복
	for (int iter = 0; iter < N; iter++)
	{
		updated = 0;
		for (int here = 1; here <= N; here++)//S -> 들러갈 노드(here)
			for (int j = 0; j < adj[here].size(); j++)// S -> 들러갈 노드 -> 도착 노드(adj[here][j])
			{
				int end = adj[here][j].first;
				int cost = adj[here][j].second;
				// 중간노드까지의 값이 INF라면 의미가 없는것은 물론,
				// 언더플로우나 오버플로우가 일어날 가능성이 존재한다.
				if (upper[here] == INF)
					continue;

				if (upper[end] > upper[here] + cost) {
					upper[end] = upper[here] + cost;
					updated = 1;
				}
			}
		if (updated == 0)// 이건 왜 들어가야하는지 정확히 모르겠다.
			break;
	}
	// 마지막 V번째 루프(음수사이클 판별)에서 완화가 일어났으면 음수 사이클 존재
	if (updated == 1) {
		upper.clear();
		cout << -1 <<'\n';
		return;
	}
	for (int i = 2; i <= N; i++)
	{
		if (upper[i] != INF)
			cout << upper[i] << '\n';
		else
			cout << -1 << '\n';
	}
}
int main() {
	// 단일 시작점 알고리즘, 음수가중치 존재
	// 음수 사이클 존재 가능, 경로 없는 경우 가능
	cin >> N >> M;
	int A, B, C;
	for (int i = 0; i < M; i++)
	{
		cin >> A >> B >> C;
		adj[A].push_back({ B,C });
	}
	bellman();
}

 

이를 코드로 짜는 것은 얼마 걸리지 않았지만, 문제는 제출이 안되고 계속 틀렸다. 알고보니 언더플로우와 오버플로우를 예상하지 못했다. 이는 실제 프로그래밍에서 더 심각한 문제를 발생할 수 있기때문에 더 주의해야한다.

결론 : 벨만-포드는 음수 가중치, 음수 사이클, O(VE) 등등의 속성을 가진다는 것을 잘 머리에 박아놓자.