취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1219번 문제인 오민식의 고민이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1219

이 문제에서는 기본적으로는 어떤 그래프 위 출발 노드에서 도착 노드로 가는 경로 중, 가중치(버는 돈)가 가장 큰 경로를 탐색하는 문제이다. 경로에 따라 돈을 벌 수도 있고 잃을 수도 있으므로, 음수 가중치를 다룰 수 있는 알고리즘인 Bellman-Ford(벨만-포드) 알고리즘이 이 문제를 해결하는 데에 적합하다. 다만, 세부적으로 나누어 출력할 대상이 많으므로 신중하게 코드를 작성해야 한다.

다음은 이 문제를 틀리지 않기 위해 주의해야하는 점들이다.

1. 가중치가 양수인 사이클(돈을 무수히 벌 수 있는 사이클)이 존재한다고 항상 답이 "Gee"가 되지는 않는다. 이 사이클을 계속 빙빙 돌면 돈을 무수히 벌 수 있는 것은 사실이지만, 돈을 벌더라도 경로의 종점이 되어야 하는 "도착 도시"로 갈 수 없다면 이러한 사이클의 존재는 의미가 없어진다.

2. 문제에서 주어진 100개의 도시가 하나의 큰 사이클을 이루고, 각 도시를 방문할 때마다 1,000,000만큼의 돈을 번다면, 각 에지를 아직 한번씩만 살펴보았는데도 100,000,000만큼의 가중치가 쌓이게 된다. 이 사이클을 100번 돌게 되면 10,000,000,000의 가중치가 쌓이게 되는데, 이는 32bit 정수의 표현범위를 넘어가는 수이다. 따라서, 이 문제를 해결하기 해서는 가중치를 저장하는 배열을 64bit 정수로 선언해야한다.

글쓴이는 이 문제의 출력조건을 아래와 같이 구분하였다.

1) 도착 도시에 도달할 수 없는 경우 "gg"를 출력

2) 가중치가 양수인 사이클(돈을 무수히 벌 수 있는 사이클) 위의 점들에서 도착 도시로 갈 수 있는 경로가 있는지 DFS로 확인 후, 존재한다면 "Gee" 출력

3) 그 외의 경우 Bellman-Ford로 계산된 경로의 최대가중치 출력

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

vector<int> G[100];
vector<int> Gi[100];
long long money[100];
int way[100][3];

vector<int> stk;
bool visited[100];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, S, E, M; cin >> N >> S >> E >> M;
	for (int i = 0; i < M; i++) {
		cin >> way[i][0] >> way[i][1] >> way[i][2];
		G[way[i][0]].push_back(way[i][1]);
		Gi[way[i][1]].push_back(i);
	}

	for (int i = 0; i < N; i++) {
		money[i] = -1000000007;
	}

	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		for (auto node : Gi[i]) {
			way[node][2] = x - way[node][2];
		}
		if (i == S) money[i] = x;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (money[way[j][0]] == -1000000007) continue;
			if (money[way[j][1]] < money[way[j][0]] + way[j][2])
				money[way[j][1]] = money[way[j][0]] + way[j][2];
		}
	}

	// cycle 위에 있는 점들을 stk에 넣고 DFS를 통해 이 점들에서 도착 도시로 갈 수 있는지 확인
	for (int j = 0; j < M; j++) {
		if (money[way[j][0]] == -1000000007) continue;
		if (money[way[j][1]] < money[way[j][0]] + way[j][2]) {
			if (!visited[way[j][0]]) {
				stk.push_back(way[j][0]);
				visited[way[j][0]] = 1;
			}
		}
	}

	// dfs
	while (!stk.empty()) {
		int current = stk.back();
		stk.pop_back();
		for (auto node : G[current]) {
			if (visited[node]) continue;
			visited[node] = 1;
			stk.push_back(node);
		}
	}

	if (money[E] == -1000000007) cout << "gg";
	else if (visited[E]) cout << "Gee";
	else cout << money[E];
}