[BOJ] 1520번 내리막 길 (Python)

[BOJ] 1520번 내리막 길 (Python)

1520번: 내리막 길

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(x, y):
    if x == m-1 and y == n-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    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 graph[nx][ny] < graph[x][y]:
                dp[x][y] += dfs(nx, ny)
    return dp[x][y]

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

참고

[백준(파이썬/Python)] 1520_내리막 길 - DFS, DP

백준 1520 내리막 길 (파이썬)