(백준) 1738번 - 골목길

문제

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

풀이

1번 노드부터 N번 노드까지 최대 비용 경로를 찾아 경로를 출력하는 문제이다. 다만, 간선의 가중치는 음수도 가능하기에, 최적의 경로가 존재하지 않는 경우가 있을 수 있으며, 이 경우 -1을 출력한다.

출발 노드가 정해져 있고, 음의 가중치가 존재하므로 벨만 포드 알고리즘을 사용하면 된다. 그러나 이 문제는 최대 비용인 경우를 찾아야 한다. 따라서 가중치의 부호를 반전시켜 최소 비용 문제로 변환한다.

이제 발생하는 음의 사이클의 경우는, 무한히 금품을 획득하는 경우일 것이다.

단순히 음의 사이클이 발생하는 경우 최적의 경로가 존재하지 않을까? 1번 노드부터 N번 노드까지의 경로에 음의 사이클이 포함되지 않을 수 있다.

그렇다면, 벨만 포드로 음의 사이클을 감지한 후, 해당 사이클의 한 노드에서 N번 노드로 도달 가능한지를 확인하면 된다. BFS나 DFS로 도달 여부를 확인하면 된다.

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

#define INF 1e9

using namespace std;

int dist[101];
int rev[101];
int visited[101];

void dfs(int node, const vector<tuple<int,int,int>>& edges) {
	for (int i = 0; i < edges.size(); i++) {
		int start = get<0>(edges[i]);
		int end = get<1>(edges[i]);

		if (node == start && !visited[end]) {
			visited[end] = 1;
			dfs(end, edges);
		}
	}
}

int main() {
	int n, m;
	cin >> n >> m;

	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({ a,b,-c }); // 가중치 부호를 반전시켜 최소 비용 문제로 변환
	}

	for (int i = 2; i <= n; i++) {
		dist[i] = INF;
	}

	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < edges.size(); j++) {
			int start = get<0>(edges[j]);
			int end = get<1>(edges[j]);
			int w = get<2>(edges[j]);

			if (dist[start] + w < dist[end]) {
				dist[end] = dist[start] + w;
				rev[end] = start;
			}
		}
	}

	// 1 -> 음의 사이클 -> n 이어야 불가능한 경우이다.
	for (int j = 0; j < edges.size(); j++) {
		int start = get<0>(edges[j]);
		int end = get<1>(edges[j]);
		int w = get<2>(edges[j]);

		// 1 -> 음의 사이클 경로가 있는가?
		if (dist[start] + w < dist[end]) {
			// 음의 사이클 -> n 경로가 있는가?
			visited[end] = 1;
			dfs(end, edges);

			if (visited[n]) {
				cout << -1;
				return 0;
			}
		}
	}

	vector<int> ans;
	int node = n;
	while (node != 0) {
		ans.push_back(node);
		node = rev[node];
	}

	reverse(ans.begin(), ans.end());

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
}

시간복잡도

벨만 포드 알고리즘에서 $O(NM)$, DFS에서 $O(NM)$이다. 내가 구현한 DFS는 모든 간선에 대해 순회하므로 다소 비효율적이나, 중요한 부분은 아니라 넘어갔다. 경로 역추적에서 $O(N)$이다. 따라서 전체 시간복잡도는 $O(NM)$이다.

공간복잡도

간선을 저장하는 edges에서 $O(M)$, dist, rev, visited 배열에서 $O(N)$, DFS의 재귀 스택에서 $O(N)$이다. $M \geq N-1$이므로 전체 공간복잡도는 $O(M)$이다.