[PS] 골목길 / C++ (백준 1738번)

골목길 (백준 1738번)

 

역시 벨만-포드 알고리즘이 기본이 되는 문제로, 1에서 n까지 가는 길에 양의 사이클이 포함되어 있는지 확인하면서 n까지 가는 경로를 출력하는 문제.

 

풀이 과정

오민식의 고민(백준 1219번)의 풀이처럼 벨만-포드 알고리즘을 적절히 구현하여 나올 수 있는 경우의 수를 모두 구해본다.

1. n까지 가는 경로 X: -1 출력
2. n 도착: 경로 출력
3. 무한 증가: -1 출력 (무한 증가 사이클의 교차점들에서 n까지 가는 경로가 존재할 때)
4. 무한 감소: 무시

• dfs나 bfs로 무한 증가 사이클의 교차점들에서 n까지 가는 경로가 존재하는지 확인한다.
  • 이때, 인접 행렬을 사용하면 편하며, 한 번 방문한 node에선, n까지 도달했으면 이미 flag를 체크했을 것이기 때문에 visit 체크를 0으로 초기화하는 과정은 모든 경로 탐색이 끝난 뒤에 해주어야 한다.
• 경로를 저장하는 방법으로는 처음엔 vector로 저장했다가 시간 초과가 나와서, be[i]: "cost[i] 값을 갱신한 i의 이전 교차로" 배열을 사용하여 마지막에 역추적하여 출력하는 방식으로 바꿨다.
  • 역추적 과정에서 사이클에 빠지는 것을 걱정할 필요가 없는 게 이전에 dfs를 돌면서 사이클을 모두 확인하기 때문에 최적의 경로가 존재하는 경우에만 역추적 함수로 들어가서 출력한다.

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

int n, m, flag = 0;
int cost[101], before[101], vi[101], be[101];
int d[101][101];
vector<pair<pair<int, int>, int> > alley;

void bellmanford() 
{
	int size = alley.size();
	for (int i = 0; i < size; i++) {
		int u = alley[i].first.first, v = alley[i].first.second, w = alley[i].second;
		if (cost[u] == 2e9)continue;
		if (cost[v] == 2e9 || cost[v] < cost[u] + w) {
			cost[v] = cost[u] + w;
			be[v] = u;
		}
	}
	return;
}

void dfs(int p)
{
	if (p == n) {
		flag = 1;
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (d[p][i]&&!vi[i]) {
			vi[i] = 1;
			dfs(i);
		}
	}
	return;
}

void print(int p) {
	if (be[p] == -1) {
		printf("1 ");
		return;
	}
	else {
		print(be[p]);
		printf("%d ", p);
		return;
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		alley.push_back(make_pair(make_pair(u, v), w));
		d[u][v] = 1;
	}

	for (int i = 1; i <= n; i++)cost[i] = 2e9;
	cost[1] = 0; be[1] = -1;
	for (int i = 1; i < n; i++)bellmanford();
	for (int i = 1; i <= n; i++)before[i] = cost[i];
	bellmanford();
	if (cost[n] == 2e9) {
		printf("-1\n");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		if (before[i] != cost[i]) {
			flag = 0;
			vi[i] = 1;
			dfs(i);
			for (int j = 1; j <= n; j++)vi[j] = 0;
			if (flag) {
				printf("-1\n");
				return 0;
			}
		}
	}
	print(n);

	return 0;
}