안녕하세요,
재재입니다.
BOJ 2176 합리적인 이동경로 문제 풀이입니다.
BOJ 2176 합리적인 이동경로
(1) 문제 설명
분류 : dynamic programming, graph
출처 : https://www.acmicpc.net/problem/2176
(1000이하) 노드가 N개인 그래프가 들어옵니다.
이때, 시작점은 1이고 도착점은 2 입니다.
합리적인 이동경로란,
이동할 때 도착점에 가까워 지며 이동하는 경우를 말합니다.
여기서, 합리적인 이동경로의 개수를 출력해주면 됩니다.
(단, 두 노드간 간선은 1개를 넘을 수 없다고 가정합니다)
(2) 풀이 도출
플로이드로는 힘들지만 다익스트라와 priority queue를 활용해서,
$$ n \log m $$ 에 모든 최단 경로를 구할 수 있습니다.
다익스트라로 구한 거리를 활용해서 dyanmic programming 으로 해결 할 수 있습니다.
dp[i] : i에서 출발했을때 가능한 합리적인 이동경로의 개수
(3) 정답 코드
BOJ 2176 합리적인 이동경로