곽로그
[12월 셋째주, DP] 내리막길 본문
문제
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
풀이
↑ → ↓ ← 순서로 이동한다고 하자.
(N-1, M-1)에 도착하게되면 파란색부분은 더이상 이동할 수 있는 방향이 없으므로 (0,3)까지 return이 된다.
그러면 다시 (0, 3)에서 ↓으로 호출을 한다.
그런데 여기서 (0, 0) ~ (N-1, M-1)로 가는 첫번째, 두번째 경로에서 중복이 발생하게 된다.
초록색으로 표시한 길은 이미 첫번째 경로에서 구했던 경로다. 다시말해 (1, 3)에 도착하면 (3,4) 로 가는 경로는 정해져 있다. 따라서 두번째에서 (3,4)에 도착하면 더이상 탐색을 하지 않아도 된다.
이를 memo[x][y]에 기록을 한다. memo[x][y]은 (x,y)에서 (N-1,M-1)으로 가는 경로의 갯수를 기록해둔다. 이 경우 memo[][]를 -1로 초기화 해서 방문했다/ 방문하지 않았다를 구분해준다. memo[x][y] 가 -1인 경우 이전에 방문한 적이 없기 때문에 (x,y) 에서 (N-1, M-1)로의 경로의 갯수를 구해야한다.
(x,y) 에서 (N-1, M-1)으로의 경로가 존재하기 위해서는 (x,y)의 이웃 칸인 (nx, ny)에서 (N-1, M-1)까지의 경로가 존재해야한다. 이때 (nx,ny)는 (x,y)의 북, 동, 남, 서 방향에 있고, 범위를 벗어나지 않으며 높이가 (x,y)보다 낮아야 한다.
따라서 memo[x][y] = f(x의 북쪽) + f(x의 동쪽) + f(x의 남쪽) + f(x의 서쪽) 이된다.