BOJ 2176 합리적인 이동 경로

S에서 T로 이동하는 합리적인 이동 경로를 구하는 문제인데, (S=1, T=2)
그리고 S에서 T로 이동할 때 T에 가까워지며 이동하는 경우, 이를 합리적인 경로라고 한다. (당연히 이 경로는 최단 경로가 아닐 수도 있다.)

문제가 이해가 잘 안되서 질문 게시판의 답변을 보고 생각을 했다.
이 문제에서 좀 애매한 것은 이동할 때, T에 가까워지며 이동한다는 것인데, 가까워진다는 것이 한 점 한 점 이동할 때, 그 점에서 T까지의 최단거리를 기준으로 가까워진다는 것을 판단하는 것일까? 최단거리가 아닌 그냥 거리라면 경우에 따라 어떤 점을 가든 거리가 멀어질 수도 있는 것이고...

일단 최단거리를 기준으로 해서 문제를 푼다면, 처음에는 플로이드로 각 점에서 각 점가지의 최단거리를 구해야하나 생각했는데, N제한이 1000이라...어떻게 할까 생각하던 중에 이런 생각이 떠올랐다. 어차피 필요한 것은 각 점에서 T까지의 최단 거리이다. 그리고 간선은 방향성이 없다고 돼있으므로 T에서의 각 점까지의 최단거리가 곧 각 점에서 T까지의 최단거리인 것이다! (사실 좀 헷갈렸는데, 다익스트라를 이용하면 T에서 각 점까지의 최단거리를 구할 수 있다.)
이제 T에서(S에서가 아님!) 각 점까지의 최단 거리를 다익스트라로 구한다.
그리고 사실 문제 분류를 봤는데 다이나믹 프로그래밍으로 분류돼 있었다. dp로 풀어보자.
d[node]=node까지 오는 합리적인 경로의 개수
d[node]=Sum(k=0~adj[node].size) d[인접노드k] (단, dist[node]<dist[인접노드k]) (dist는 각 점에서 T까지의 최단거리)
음 내가 식을 내 힘으로 세워보다니... 맞을지는 모르겠지만, 그리고 문제가 쉬운 문제일 수도 있겠지만.. 감격이다. 한 번 이대로 풀어봐야겠다.
기저 사례는 S로 해줘야할 것 같다. node가 S인 경우 경로의 개수를 1로 return해준다. S에서 출발하지 않으면 아무 의미가 없기 때문이다. 문제에서 구하는 것은 S에서 출발해서 T로 가는 합리적인 경로이므로...

중간에 INF값을 내가 int형 최대값으로 설정하려고 2<<31-1로 해놓은 것에서 아마 2<<31에서 int형 범위를 넘어서 좀 문제가 생긴 것 같아 그냥 2e9(20억)으로 설정하고 했다.
와우 AC를 받았다!!!