문제

• 
• 시간 제한: 2초
• 메모리 제한: 512MB

Problem Analysis

출발지에서 시작하여 가능한 모든 경우를 조사해야 한다. 이때, 다음과 같이 반복적으로 접근하는 부분이 있기 때문에 dp로 풀 수 있다. 또한, Cycle이 있을 경우 무한 번 이동할 수 있으므로 DFS 시에 찾아주어야 한다.

Algorithm

DFS를 하면서 Dynamic Programming을 시행한다.
1. 다음에 갈 수 있는 칸이, 이미 recursive stack에 존재한다면, Cycle로 판정한다.
2. 다음에 갈 수 있는 칸에서 갈 수 있는 최대 경로를 이미 알고 있다면 이를 참고한다.
3. 다음에 갈 수 있는 칸에서 갈 수 있는 최대 경로를 모르면, recursive call을 한다.

Data Structure

• dp[N][M]: 각 칸에서 갈 수 있는 최대 경로를 저장
• recStack[N][M]: 각 칸이 recursive stack에 존재하는지 나타내는 flags

결과

other

시간 복잡도는 O(NM)이다.