백준 1738(골목길) 벨만포드

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

1738번: 골목길

 

벨만포드 알고리즘을 알고 있으면 딱 봐도 벨만포드 알고리즘을 사용하는 문제같다. 왜냐하면 음수간선이 존재하고, 사이클이 존재하는지도 확인을 해야하는 문제이기 때문.

 

문제에서 지나갈 때마다 계속해서 돈을 줍고, 잃는다고 하니 그냥 일반 최단거리 문제처럼 풀 수 있다. 

 

아 그런데 여기서 돈을 최대한 적게 뺏기고, 많이 얻어야 하므로, 최대거리를 구하는 문제가 된다. 역시 말장난일 뿐이니깐 값을 음수로 집어넣고, 최단거리로 문제를 풀어보자.

 

========================================================================================================================================================

벨만포드는 꼭지점의 갯수만큼 이어진 간선으로 거리를 갱신한다. 

 

꼭짓점의 갯수의 횟수만큼 반복하는 이유는 조사의 순서가 뒤바뀌어서 원하는 결과가 안 나올수 있기 때문이다. 

다 익스트라를 생각해보자. 

다 익스트라 알고리즘은 최단거리를 구하기 위해서 가장 최단 거리를 이용하는 방법을 사용한다. 

 

최단 거리 = 최단거리들의 집합으로 이루어진다. 

 

따라서 만약에 1에서 3으로 이동하는 경우를 생각해보자 

 

1. 1->3 = 10

2. 1->2 = -4

3. 2->3 = -3

4. 1->5 = 0

5. 5->2 = -10

 

이런식으로 간선이 이루어졌다고 생각해보자 

 

1. dist[3] = 1->3 으로 가는 경우 10으로 저장, 

2. dist[2] = -4

3. dist[3] > dist[2] + cost 이므로 dist[3]을 -7로 갱신

4. dist[5] = 0

5. dist[2] > dist[5] + cost이므로 dist[2]를 -10으로 갱신

 

자 여기서 확인해야 할 것은 dist[3]이 진짜 최단거리값을 담고 있느냐인데, 

 

1-5-2-3 인 경우를 갱신하지 못 했다. 

따라서 최악의 경우를 생각해서 정점-1 번 반복을 해야한다. 

 

그러면 cycle을 발견하는 방법은 무엇일까? 

 

최단거리로 갱신을 완료했다고 하자. 

서울에서 부산가는 경우 거리를 100번 계산해도 갱신이 되지 않듯이, 일반적인 경우에는 정점-1번 반복후에 값의 변화가 없다.

 

하지만 음의 간선으로 이루어진 cycle이 존재하는 경우에는 계속해서 시간이 줄어들 것이다. 따라서 정점의 횟수를 돌려봤을때에도 변화가 있다면 -> cycle이 존재하는 경우이다. 

========================================================================================================================================================

 

 

이제 문제로 돌아와서 문제에서 핵심은 단순 사이클의 존재여부가 아니다. 

1에서 n으로 갈때, cycle이 존재하느냐이다. 

따라서 만약 cycle이 존재하는 지점을 발견했을때, 그 지점에서 n까지 갈 수 있고, 1에서 그 지점까지 갈 수 있느냐가 문제의 핵심이라고 할 수 있다. 

 

이 방법을 계속 생각하다가 도저히 모르겠어서 구글링해서 도움을 받았다. 

	q.push(n);
	visit[n] = true;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < rev[cidx].size(); i++) {
			int next = rev[cidx][i];
			if (!visit[next]) {
				visit[next] = true;
				q.push(next);
			}
		}
	}

 

 

bool visit 배열과 역추적을 이용하는 방법이다. 

 

 

경로를 찾는 방법은 parent 배열을 이용해서 그리고 어차피 마지막에 갱신된게 최단 거리로 가는 방법이니깐, 그 특성을 이용해서 코드를 구성하였다. 

 

출력은 따로 재귀함수를 이용해서 출력했다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define MAX 101

int n, m, u, v, w, INF = 987654321;
int parent[MAX];
int dist[MAX];
vector<int> rev[MAX];
vector<pair<pair<int, int>, int> > road;
queue<int> q;
bool cycle;
bool visit[MAX];

void solve() {
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < road.size(); j++) {
			int from = road[j].first.first;
			int to = road[j].first.second;
			int cost = road[j].second;
			if (dist[from] == INF) continue;
			if (dist[to] > dist[from] + cost) {
				if (i == n && visit[from]) {
					cycle = true;
				}
				dist[to] = dist[from] + cost;
				parent[to] = from;
			}
		}
	}
}

void find_route(int s) {
	if (s == 1) {
		cout << s << " ";
		return;
	}
	find_route(parent[s]);
	cout << s << " ";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		road.push_back(make_pair(make_pair(u, v), -w));
		rev[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	parent[1] = 1;
	
	q.push(n);
	visit[n] = true;
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		for (int i = 0; i < rev[cidx].size(); i++) {
			int next = rev[cidx][i];
			if (!visit[next]) {
				visit[next] = true;
				q.push(next);
			}
		}
	}


	solve();

	if (cycle) {
		cout << -1 << "\n";
		return 0;
	}

	find_route(n);


}

 

 

무엇이 필요한지, 문제를 읽고 바로 알아차리는 능력이 떨어지는 것 같다. 

한번에 좀 맞춰보자