-1 : 아직 한 번도 탐색하지 않은 좌표
0 : 목표 지점까지 경로가 없는 좌표
그리고 목표 지점까지 갈 수 있는 좌표라면, 방문한 횟수에 따라 수가 올라갈 것이다.
1. dp 테이블을 -1로 초기화 한 후 dfs함수를 돌려 만약 x,y가 M-1,N-1 즉 좌표의 도착점 까지 도달한다면 1을 리턴하여 더해준다.
2. x,y의 좌표가 -1이 아니라면 방문 한 적이 있는 좌표므로 그 값을 리턴하여 더해준다.
3. 일단 좌표를 0으로 초기화 해서 4방향 dfs를 수행하여도 갈 수 있는 곳이 없다면 0을 리턴
4. 경로가 있다면 정상적으로 dfs를 수행.
5. 출발지가 결국 경로의 수가 됨
dp테이블
[3, 2, 2, 2, 1]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, -1]
'알고리즘 문제 > 다이나믹 프로그래밍' 카테고리의 다른 글
| 배낭 (평범한 배낭 문제) (0) | 2022.01.22 |
|---|---|
| 다이나믹 프로그래밍 (가장 긴 증가하는 부분 수열 LIS) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 (탑다운 형식) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 문제 (마지막을 선택해야 하고 연속해서 뽑지 못하는 수열에서 최댓값 찾기) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 (연속해서 뽑지 못하는 수열에서 최댓값 찾기) (0) | 2022.01.19 |