[알고리즘] 백준 - 1520 (내리막 길) / 파이썬

import sys
sys.setrecursionlimit(10**9)

m ,n  = map(int, sys.stdin.readline().split())
array = [list(map(int,sys.stdin.readline().split())) for _ in range(m)]
dp = [[0] * n for _ in range(m)]
check = [[False] * n for _ in range(m)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def DFS(x,y):
    if(x == n-1 and y == m-1):
        return 1
    if(check[y][x]):
        return dp[y][x]

    for i in range(4):
        nx = dx[i] + x
        ny = dy[i] + y
        if(0<= nx < n and 0<= ny < m):
            if(array[ny][nx] < array[y][x]):
                dp[y][x] += DFS(nx,ny)
    check[y][x] = True
    return dp[y][x]
print(DFS(0,0))