BOJ 2176 합리적인 이동경로

* BOJ 2176 합리적인 이동경로

[분류 : 다이나믹 프로그래밍/ 최단 경로]

  분류에서 보이듯 굉장히 희한한 문제다. 심지어 그래프 + 다이나믹인데, 트리 + 다이나믹은 익숙하지만 이런 조합은 처음 봤다.

[풀이]

  S에서 T로 가능 경로는 반드시 T로 가까워져야 한다는 조건이 있는데, 이는 거꾸로 말하면 T로 멀어지면 안된다는 뜻이다. 보다 정확하게 말하면 S에서 T로 가능 경로 중에 사용된 간선 집합을 P라고 정의할 때, 방향 간선 (u, v)에 대해 u 위치에 있을 때보다 v로 이동하면 T에 더 가까워져야 함을 알 수 있다.

  정리하면 아래처럼 정의할 수 있다.

증명)

  역으로 u가 v보다 T로부터 가깝다고 하자(du < dv). 그렇다면 현재 위치 u까지 왔을 때, T에 가까워지기 위해서는 v로 이동했을 때의 거리가 현재보다 작아야 하는데, 그렇지 못함을 바로 자명하게 알 수 있다. 따라서 T에 가까워지기 위한 최소 조건은 위에 있는 수식을 만족해야함을 알 수 있습니다.

구현)

  최단 경로는 일반적인 가중치 최단거리 알고리즘 하나를 골라서 사용하면 됩니다. 가중치가 양수이니 벨만을 써도 상관 없구요. 저는 간단하게 SPFA를 사용했습니다.

  이후 다이나믹 구성은 현재 위치에 대해 위 수식이 만족하는지만 확인하면 되므로 꽤 간단하게 구현할 수 있습니다.

(만약 가중치 C가 0이란 값을 가질 수 있었다면 어떻게 됐을런지..)

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int MAX_N = 1e3;
struct _d { int v, w; };
vector<_d> adj[MAX_N];
int N, dist[MAX_N], dp[MAX_N];
int rec(int u) {
	int& ret = dp[u];
	if (ret != -1) return ret;
	if (!u) return ret = 1;
	ret = 0;
	for (_d& e : adj[u]) {
		if (dist[u] < dist[e.v])
			ret += rec(e.v);
	}
	return ret;
}

int main() {
	int M, A, B, C;
	queue<int> q;
	bool hasQ[MAX_N] = {};
	scanf("%d%d", &N, &M);
	while (M--) {
		scanf("%d%d%d", &A, &B, &C);
		A--, B--;
		adj[A].push_back(_d{ B, C });
		adj[B].push_back(_d{ A, C });
	}
	memset(dist, 0x3F, sizeof dist);
	q.push(1);
	dist[1] = 0;
	while (!q.empty()) {
		int u = q.front(); q.pop();
		hasQ[u] = 0;
		for (_d& e : adj[u]) if (dist[e.v] > dist[u] + e.w) {
			dist[e.v] = dist[u] + e.w;
			if (!hasQ[e.v]) {
				q.push(e.v);
				hasQ[e.v] = 1;
			}
		}
	}
	memset(dp, -1, sizeof dp);
	printf("%d", rec(1));
	return 0;
}