백준 1865 번 : 웜홀

문제 접근

---

음수 사이클을 찾는 문제이기 때문에 다익스트라 알고리즘로는 제대로 풀지 못할 수 있다. 알고리즘 문제 해결 전략 책에서 벨만-포드 알고리즘을 공부하고 이 문제를 풀었다.

 

벨만-포드 알고리즘은 각 정점까지의 최단 거리의 상한을 담은 배열 upper[] 를 relax 하는 과정을 통해 최단 거리를 찾는 알고리즘이다. 다만 최단 거리를 구할 때 특정 한 정점까지의 최단 거리를 갱신하면서 구하는 다익스트라와는 달리 벨만-포드 알고리즘은 relax(완화) 하는 과정을 V-1 번 거치기에 음수 간선이 있을 때의 최단 거리 또한 판단할 수 있으며, 음수 사이클의 존재 여부는 V 번째에 완화가 되는지로 판단해서 음수 사이클까지 확인할 수 있다.

 

동작 과정은 이해가 되는데 풀이에 대한 감각이 아직 느껴지지 않아서 다익스트라, 벨만-포드, 플로이드의 알고리즘을 이용해야 하는 다양한 문제들을 풀어보려고 한다. 원래는 Class4 Essential 을 다 풀고 블로그 정리 작업을 하거나, 다른 알고리즘들 공부를 해보려고 했는데 생각해보니 목적을 위한 수단에 먹혀버린 느낌이 나서 다 한번에 하려고 한다.

 

욕심 좀 부려보겠다.

 

 

문제 코드

---

#include <iostream>
#include <vector>

using namespace std;

vector<pair<int,int>> adj[501];
int TC, N, M, W;
// 최단거리의 최댓값은 25000000 이기의 INF 값에 이 값을 넣었다.
const int INF = 25000001;

bool bellmanFord()
{
	// 나는 0부터 값을 넣은 게 아니라 1부터 넣었기에 N+1 해야 한다.
	vector<int> upper(N+1, INF);
	
	upper[1] = 0;
    // 완화되었는지 확인하는 변수
	bool update;
	
	for(int iter=0; iter<N; ++iter)
	{
		update = false;
        // 마찬가지로 값을 1부터 넣었기에 1~N 이 되어야 한다.
		for(int here=1; here<=N; ++here)
		{
			for(int i=0; i<adj[here].size(); ++i)
			{
				int there = adj[here][i].first;
				int cost = adj[here][i].second;
				
				//cout<<"Compare "<<there<<"("<<upper[there]<<") and "<<here<<"("<<upper[here]+cost<<")\n";
				
				if(upper[there] > upper[here] + cost)
				{
					upper[there] = upper[here] + cost;
					update = true;
					//cout<<"[Updated] "<<here<<" -> "<<there<<'\n'; 
				}
			}
		}
        // 완화가 이루어지지 않았다면 이미 모든 값이 최단 거리라는 뜻이므로 break;
		if(!update)
			break;
	}
	
    // V 번째에서 완화가 이루어지는 음수 사이클이 있다는 것이므로 true 를 return 한다.
	if(update)
		return true;
	
	else
		return false;
}

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>TC;
	
	while(TC--)
	{
		for(int i=0; i<501; ++i)
			adj[i].clear();
		
		int S, E, T;
		
		cin>>N>>M>>W;
		
		while(M--)
		{
			cin>>S>>E>>T;
            // 도로는 양방향 간선
			adj[S].push_back(make_pair(E,T));
			adj[E].push_back(make_pair(S,T));
		}
		
		while(W--)
		{
			cin>>S>>E>>T;
            // 웜홀은 단방향 간선
			adj[S].push_back(make_pair(E,-T));
		}
		
		if(bellmanFord())
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
}