백준 1520 [python]

https://www.acmicpc.net/problem/1520

import sys
sys.setrecursionlimit(10000)

def find(x, y, val):
    if x == M - 1 and y == N - 1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    
    dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    dp[x][y] = 0
    
    for i in range(4):
        if x + dir[i][0] == -1 or x + dir[i][0] == M or \
        y + dir[i][1] == -1 or y + dir[i][1] == N:
            continue
        
        if val > m[x + dir[i][0]][y + dir[i][1]]:
            if dp[x + dir[i][0]][y + dir[i][1]] != -1:
                dp[x][y] += dp[x + dir[i][0]][y + dir[i][1]]
            else:
                dp[x][y] += find(x + dir[i][0], \
                y + dir[i][1], m[x + dir[i][0]][y + dir[i][1]])
    return dp[x][y]
            
M, N = map(int, input().split())
m = []
dp = [[-1 for i in range(N)] for i in range(M)]
for i in range(M):
    m.append(list(map(int, input().split())))
    
print(find(0, 0, m[0][0]))

무지성 길찾기에 DP를 적용할 수 있는 이유는 크기가 큰 수부터 작은수로 이동하는 방향이 정해져있기 때문이라고 생각했다. 따라서 블럭마다 그 위치에서 종점에 도착하는 경우의 수를 저장하면, 이 블럭으로 이동하기 이전 블럭으로 역류할 가능성이 없기 때문에 그냥 네 방향의 블럭들의 도착 가능한 경우의 수를 더해주면 정답이 된다.

코드는 많이 더럽지만 혼자 힘으로 풀어서 뿌듯하다.