[Python] BOJ 1520 - 내리막 길(DFS + DP)

www.acmicpc.net/problem/1520

1520번: 내리막 길

(0, 0)에서 (M-1, N-1)까지 이동 가능한 경로의 수를 모두 구해야 하기 때문에 단순히

DFS로는 풀 수 없고, DP를 통해 메모이제이션까지 써야 한다.

 

1. N * M크기의 지도 m을 입력받고, dp배열을 만들고 -1로 채운다.

2. dp[i][j] = (i, j)까지 이동하는 경로의 수

3. (M-1, N-1)부터 상하좌우 방향을 탐색하며 dp[x][y]에 dfs(nx, ny)값을 더해준다.

   -> (x, y)가 방문하지 않은 점이라면(dp[x][y] = -1) dp[x][y]를 0으로 바꿔주고 dfs(nx, ny)값을 더해준다.

4. dp[0][0] = 1

5. 최종적으로 dp[M-1][N-1]을 출력하면 (M-1, N-1)까지 이동 가능한 경로의 수이다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
dx = [1,-1,0,0]
dy = [0,0,-1,1]
def dfs(x, y):
    if x == 0 and y == 0:
        return 1
    if dp[x][y] == -1:
        dp[x][y] = 0
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < M and 0 <= ny < N:
                if m[x][y] < m[nx][ny]:
                    dp[x][y] += dfs(nx, ny)
    return dp[x][y]

M, N = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(M)]
dp = [[-1] * N for _ in range(M)]
print(dfs(M-1, N-1))

(solved.ac 티어: 골드 4)