[ Algorithm / 벨만 포드 알고리즘 ] + 백준 1865 웜홀 문제풀이

 

"벨만 포드(bellman-ford) 알고리즘 "

 

알고리즘 이름이 맘에 안든다. =3= 알고리즘이나 수학적 법칙을 보면 발견한 사람들의 이름으로 이름을 만든다. 직관적이지 않아서 계속 까먹게 된다. 직관적으로 이름을 지어줬으면 좋겠다. 예를 들어, "음수사이클 다익스트라" 이런식으로 ~

 

---

 

1. 최단 경로 트리 (shortest-path tree), 최적해 구조(optimal substructure 알고리즘이다. 

답은 여러개가 존재 할 수 있으면 가중치가 있는 그래프로 최단 경로를 찾는다. 

 

2. 음수 사이클의 유무를 확인할 수 있다. 

다익스트라랑 다른 점!!으로 음수 사이클의 발생으로 최단 경로가 무한으로 빠지는 음수차이클을 찾는다. 

 

3. 모든 음수 간선이 문제다 ? 

아니다. (-) 마이너스 값이 있는데 단순하게 경로 위에 있어서 그 경로를 음수로 만들지 않는다면 문제가 없다. 

시작점에서 도달 가능한 음수 순환이 문제가 될 때(B와 같은 경로) 벨만포드 알고리즘으로 피해줘야한다. 

(A). 사이클이 돌 때 값이 점점 더 커짐 - 문제없음

(B). 사이클이 돌 때마다 -2씩 경로가 점점 줄어듦 - 문제있음

4. 어떻게 찾아내는가 ?

(정점 -1)번의 매 정점을 추가하면 모든 간선을 전부 확인하면서 노드간의 최단거리를 갱신한다. 한 번 모두 돌고 한 번 더 루프를 돌렸을때 간선이 또! 더 작은 값으로 갱신되는게 있다면 음수 사이클이 존재한다. 

 

5. 문제를 풀면서 알아보자.

 

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

 

• N개 지점
• M개 도로 ( 방향 x ) 
• W개 웜홀 ( 방향 o ) : 윔홀 내에서는 시계가 거꾸로 간다고 생각하면 된다.

 

1) 모두 돌고 한 번 더 루프

 

2) Relax연산을 사용.

모든 간선에 대해 Relax를 수행한다.

#include<iostream>
#include<vector>
#include<tuple>
#include<limits.h>
using namespace std; 

vector<long>dist;

int main(void)
{
	int Tc;
	cin >> Tc; 

	while (Tc--)
	{
		int N, M, W; 
		cin >> N >> M >> W; 

	    vector<tuple<int, int, int>> edges; 

		for (int i = 0 ; i < M; ++i) // 도로의 정보
		{
			int S, E, T; 
			cin >> S >> E >> T; 
			edges.push_back(make_tuple(S, E, T));
			edges.push_back(make_tuple(E, S, T));
		}

		for (int i = 0; i < W; ++i) // 웜홀의 정보
		{
			int S, E, T;
			cin >> S >> E >> T;
			edges.push_back(make_tuple(S, E, -T));
		}
        
		dist.resize(N + 1);	
		fill(dist.begin(), dist.end(), INT_MAX);

		bool cycle = false; 
		dist[1] = 0; 
		for (int i = 1; i <= N; ++i) // (n-1)번 반복.
		{
			for (int j = 0; j < edges.size(); ++j) // "모든 간선" 하나씩 확인한다.  
			{
				int from = get<0>(edges[j]); 
				int to = get<1>(edges[j]);
				int cost = get<2>(edges[j]);

				if (dist[to] > (dist[from] + cost))
				{	
                    if (i == N)
					{
						cycle = true; 
                        break;
					}
					dist[to] = dist[from] + cost; 
				}

			}
		}

		if (cycle)
		{
			cout << "YES\n";
		}
		else
		{
			cout << "NO\n" ; 
		}
	}
	
	return 0;
}

※ 14%에서 계속 틀리고 있다면? "YES", "NO" 소문자 대문자 확인하기!