백준 1520 내리막 길 (DP)

direction = [[1,0], [-1,0], [0,1], [0,-1]]

def dfs(m,n, x, y):
    if x == m-1 and y == n-1:
        dp[x][y] = 1
        return
    if dp[x][y] != -1:
        return
    dp[x][y] = 0

    for d in direction:
        nx, ny = x+d[0], y + d[1]
        if 0<= nx < m and 0 <= ny < n and maps[x][y] > maps[nx][ny]:
            dfs(m,n,nx,ny)
            dp[x][y] += dp[nx][ny]

    
m, n = [int(v) for v in input().split()]
maps = [[0]*n for _ in range(m)]
dp = [[-1]*n for _ in range(m)]

for i in range(m):
    maps[i] = list(map(int, input().split()))

dfs(m, n,0, 0)

print(dp[0][0])

이 문제의 핵심은 DFS로 진행해 나갈 때 이미 진행했었던 길이라면 다시 계산하지 않는 것이다.

이를 위해 dp 초기 값은 -1로 저장해 둔다. -1로 함으로서 해당 좌표에 대해 계산 수행할 때 계산을 했음에도 0인 경우와 구분할 수 있다. 즉 해당 좌표에 대해 방문 했는데 0인 경우와 방문하지 않은 경우를 구분하기 위함이다.

이후 진행할 수 있다면 즉 다음으로갈 좌표에 해당하는 값이 현재 값보다 작다면 dfs 진행하며 현재 좌표 dp에 해당 값을 더해주면서 진행한다.

이렇게 함으로써 이미 계산을 진행한 좌표의 경우 다시 dfs를 진행하지 앟아 연산시간을 줄일 수 있다.