[알고리즘] 백준 1219 오민식의 고민

📖문제

1219 오민식의 고민

💡구상

우선 문제를 잘 살펴보면 그래프 간의 가중치는 "버는 돈" 에서 "교통 비용"을 뺀 값이고, 음수가 될 수 있다.

음수 가중치를 지닌 그래프의 최단 경로??
벨만포드 알고리즘이 떠올라야 한다.

그런데 이 문제는 단순히 최단거리를 구하는 것 뿐만 아니라, 순환 여부까지 탐지를 해야하므로 난이도가 꽤 있다.

이는 어떻게 해결해야 할까? 코드를 살펴보자.

🔍코드

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n,m,S,E,s,e,p;
vector<pair<int,int>> route[51];
long long dist[51],price[51],visited[51];
queue<int> q;
bool flag;
int main() {
	// 입력 
	cin>>n>>S>>E>>m; 
	for(int i=0; i<m; i++){
		cin>>s>>e>>p;
		route[s].push_back({e,p});
	}
	for(int i=0; i<n; i++){
		cin>>price[i];
	}
	
	// 벨만포드 
	fill(dist,dist+51, -INF);
	dist[S] = price[S];
	for(int i=0; i<n; i++){
		for(int here=0; here<n; here++){
			for(auto there : route[here]){
				int now = there.first;
				int now_dist = there.second;
				if(dist[here] != -INF && dist[now] < dist[here] + price[now] - now_dist){
					dist[now] = dist[here] + price[now] - now_dist;
					// 사이클이 발생한다면 
					if(i==n-1){
						q.push(here);
					}
				}
			}
		}
	}
	
	// 사이클 탐색 
	while(q.size()){
		int here = q.front();
		q.pop();
		for(auto there : route[here]){
			if(there.first = E){
				flag = true;
				break;
			}
			if(!visited[there.first]){
				visited[there.first] = 1;
				q.push(there.first);
			}
		}
		if(flag) break;
	}
	
	// 출력 
	if(dist[E] == -INF) cout<<"gg";
	else if(flag) cout<<"Gee";
	else cout<<dist[E];
	
	return 0;
}

벨만포드

먼저 벨만포드 알고리즘의 동작과정부터 살펴보자.

벨만포드 알고리즘의 동작 과정

1. 최단거리 배열을 초기화한다.
2. 모든 노드를 탐색하며 아래의 과정을 수행한다.
   2.1. 현재 노드와 연결된 간선들을 탐색한다.
   2.2. 간선이 조건에 해당한다면 갱신한다.
3. 이를 n-1번 반복한다.

	// 초기화
	fill(dist,dist+51, -INF);
	dist[S] = price[S];
    // n번 반복
	for(int i=0; i<n; i++){
    	// 모든 노드 탐색
		for(int here=0; here<n; here++){
        	// 노드와 연결된 간선 탐색
			for(auto there : route[here]){
				int now = there.first;
				int now_dist = there.second;
                // 갱신
				if(dist[here] != -INF && dist[now] < dist[here] + price[now] - now_dist){
					dist[now] = dist[here] + price[now] - now_dist;
					// 사이클이 발생한다면 
					if(i==n-1){
						q.push(here);
					}
				}
			}
		}
	}

하지만 왜 n번 탐색했을까?

이 문제는 갱신 이후에 사이클을 판단해야 한다.
벨만포드 알고리즘은 n-1번 수행 후 갱신이 완료된다. (자신을 제외한 n-1개의 노드에 대해 탐색을 완료했기 때문)

하지만 n-1번 이후에 갱신이 일어난다면?? 사이클이 존재한다고 볼 수 있다.
이 문제의 경우 최댓값일 경우 갱신이 일어나므로 양의 사이클이라 볼 수 있다.

사이클 탐색

하지만 이 문제는 사이클 여부를 확인하는 것이 아니라 목적지와 사이클이 연결되어 있는지 여부를 확인해야 한다.

그러려면 해당 사이클이 일어나는 노드와 목적지 노드가 연결되어있는지 확인하면 된다.
만약에 연결되어 있다면? 목적지의 값도 무한으로 양으로 갱신될 것이다.

그래서 벨만포드 알고리즘 탐색 중에 사이클이 일어나는 노드들을 큐에 저장해놓고, 탐색이 끝난 이후 BFS 로 연결 여부를 확인해주면 된다.

while(q.size()){
		int here = q.front();
		q.pop();
		for(auto there : route[here]){
			if(there.first = E){
				flag = true;
				break;
			}
			if(!visited[there.first]){
				visited[there.first] = 1;
				q.push(there.first);
			}
		}
		if(flag) break;
	}

🔥배운 점

여러 알고리즘을 복합적으로 함께 사용하는 것은 언제나 어려운것 같다. 사이클에 대한 문제에 자신이 없었는데 이 문제를 통해서 맷집을 키운 느낌인것 같다. 문제를 풀 때 풀이 방법으로 알고리즘을 떠올리는것은 당연하지만, 이를 유기적으로 함께 사용하는 능력을 더 키워야 할 것 같다.