문제: 11657번: 타임머신  

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m; // n: 도시의 개수, m: 버스 노선의 개수
	cin >> n >> m;
	vector<pair<pair<int, int>, int>> edges;

	// 버스의 노선 정보
	for (int i = 0; i < m; i++) {
		int a, b, c; // a: 시작도시, b:도착도시, c:이동시간
		cin >> a >> b >> c;
		edges.push_back(make_pair(make_pair(a, b), c));
	}

	// 1번 도시를 시작 정점으로 고정..
	// distance 를 int 가 아니라 long long ㅡ로 선언해야함..
	// 500개 vertex, 6000개 edge 가 -10000 일 경우 최솟값 계산이라 -30억이 나올 가능성 있다..
	vector<long long> distance((n + 1), INT_MAX); // 시작점과의 거리 저장
	distance[1] = 0; // 시작점에서 시작점으로 거리는 0임
	
	// (정점개수-1) 만큼 반복해야함
	// 경로에 포함된 간선 수는 최대 (정점개수-1) 개이기 때문에
	// 음의 사이클이 존재하는 경우는 (정점개수-1) 회 이후에도 더 짧아지는 경로 발생
	for (int i = 0; i < n - 1; i++) {
		// 모든 간선을 돌아야함
		for (int j = 0; j < m; j++) {
			pair<pair<int, int>, int> edge = edges[j]; // 간선 가져오기
			int u = edge.first.first; // 간선 시작
			int v = edge.first.second; // 간선 도착
			int w_uv = edge.second; // 가중치

			// 본래 값보다 작으면 값 업데이트
			if ((distance[u] != INT_MAX) && distance[u] + w_uv < distance[v]) {
				distance[v] = distance[u] + w_uv;
			}
		}
	}

	bool flag = false;
	// 한 번 더 해봤을 때 더 짧아지는 경로가 발생하면 음의 사이클이 존재함!
	for (int i = 0; i < m; i++) {
		pair<pair<int, int>, int> edge = edges[i];
		int u = edge.first.first; // 간선 시작
		int v = edge.first.second; // 간선 도착
		int w_uv = edge.second; // 가중치

		// 어떤 노드 u 로 가는 경로가 발견되지 않은 상태(distance[u] == INT_MAX)라면, 그 노드를 경유하는 경로도 업데이트 되지 않음.
		// v-1 번의 반복을 통해 간선 정보를 충분히 전달해야 모든 노드의 거리가 제대로 갱신됨..
		// 아 그래서 첫 번째 반복에서는 직접적으로 연결된 노드들만 업데이트되고
		// 두 번째 반복에서는 한 번 거쳐서 연결된 노드들이 업데이트 됨
		// 즉, 이 과정을 v-1 번 반복해서 최대 v-1 개의 간선을 거치는 모든 경로 계산
		if ((distance[u] != INT_MAX) && (distance[u] + w_uv < distance[v]))
			flag = true; // 음의 사이클 존재하면 flag 값을 true 로 바꿔주기..
	}

	if (flag)
		cout << -1 << "\n";
	else {
		// 시작정점 번호 1임. 자기 자신으로 가는 거리는 출력 안 할 것.. 문제 조건이 그런 듯..
		for (int i = 2; i < n + 1; i++) {
			// 음의 사이클이 존재하는 경우랑, 해당 도시로 가는 경로가 없을 때 -1 출력..
			if (distance[i] == INT_MAX)
				cout << -1 << "\n";
			else
				cout << distance[i] << "\n";
		}
	}


	return 0;
}

 

... 아 진짜 너무 어려웠다. 어려운건 둘째치고 틀린 부분 발견해서 고치고 낼 때마다 또 틀리는 부분이 있어서 기분이 너무나빴다. 

 

아무튼 이 문제는 음수 가중치가 입력으로 주어지기 때문에 기존 다익스트라 알고리즘으로는 문제를 해결할수가 없다. 음수 가중치를 허용하는 알고리즘으로는 대표적으로 벨만포드 알고리즘이 있다.

 

벨만포드 알고리즘과 다익스트라 알고리즘을 비교하는 정말 좋은 글이 있어서 가져와보았다.

 

출처: [알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

더보기

[다익스트라 알고리즘]

  • 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
  • 음수 간선이 없다면 최적의 해를 찾을 수 있다. (음수 간선이 있을 때는 최적의 해를 찾을 수 X)
  • 시간 복잡도가 빠르다. (OElogV) --> 개선된 다익스트라 알고리즘 (우선순위 큐 사용)

 

[벨만-포드 알고리즘]

  • (정점 - 1)번의 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. (<-->다익스트라와 차이점은 매 반복마다 모든 간선을 확인한다는 것이다. 다익스트라는 방문하지 않은 노드 중에서 최단 거리가 가장 가까운 노드만을 방문한다.)
    • 다익스트라 알고리즘에서의 최적의 해를 항상 포함하게 된다.
  • 음수 간선이 있어도 최적의 해를 찾을 수 있다. (음수 간선의 순환을 감지할 수 있기 때문이다.)
  • 시간 복잡도가 느리다. O(VE)

 

※ 모든 간선의 비용이 양수일 때는 다익스트라를, 음수 간선이 포함되어 있으면 벨만-포드를 사용하면 된다.

 

아무튼 벨만 포드 알고리즘의 핵심은 모든 간선에 대해 d[v] 와 경로를 갱신하는데 이를 (정점개수-1) 회 반복한다. 경로에 포함된 최대 간선 수는 (정점개수-1) 개이기 때문이다. 

 

마지막으로 이를 한 번 더 수행했을 때 전보다 값이 작아지는 경우가 있다면 이는 음의 사이클이 있음을 의미한다. 

 

더보기

// 어떤 노드 u 로 가는 경로가 발견되지 않은 상태(distance[u] == INT_MAX)라면, 그 노드를 경유하는 경로도 업데이트 되지 않음.
// v-1 번의 반복을 통해 간선 정보를 충분히 전달해야 모든 노드의 거리가 제대로 갱신됨..
// 아 그래서 첫 번째 반복에서는 직접적으로 연결된 노드들만 업데이트되고
// 두 번째 반복에서는 한 번 거쳐서 연결된 노드들이 업데이트 됨
// 즉, 이 과정을 v-1 번 반복해서 최대 v-1 개의 간선을 거치는 모든 경로 계산

 

처음에는 강의자료 사진을 봤을 때 모든 간선에 대해 계산을 한다고 했으면서 무한대의 값이 남아있는 모습이 이해가 안 됐었는데 오늘 문제를 풀면서 알게 되었다. 반복문을 한 번 돌면 직접적으로 연결된 노드들만 업데이트 되고, 두 번째 반복에서는 한 번거쳐서 연결된 노드들이 업데이트 되는 것이었다. 역시 눈으로 보는 거랑 직접 풀어보는 거랑은 이해도 차원에서 많이 차이가 나는 것 같다..

 

 

내일도 복습하고 다시 풀어봐야겠다...

 

 

 

 

참고자료: 

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

 

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

벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?

velog.io

 

티스토리툴바