문제

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

Problem Analysis

답을 구하는 특별한 수식이 존재하지 않는다. 모든 칸을 조사해 보아야 하는데, 현재 칸에서의 최대는, 상하좌우 인접칸에서 시작할 때의 최대 + 1 이다. 즉, Sub-Problem이 반복되는 것이므로, Dynamic Programming으로 풀 수 있다.

Algorithm

1. 현재 칸에서 이동 가능한 상하좌우 칸을 조사한다
   • 이미 조사했다면, 저장된 값을 참조
   • 그렇지 않다면, recursive call
2. 조사한 상하좌우 칸의 최댓값 + 1을 현재 칸에 저장
3. 조사하지 않은 칸이 있다면, 1로 돌아가 조사

Data Structure

• forest[n][n]: 대나무 숲 저장
• dp[n][n]: 각 칸의 최대 저장

결과

Other

시간 복잡도는 DFS가 O(V+E)이므로, O(N^2)이다.