boj 1520 내리막길 python

DFS에 대한 이해와 DP에 대한 이해가 필요했던 문제.

500*500 이니 일반적인 dfs로는 TLE가 뜬다.

이미 해당 경로를 방문 했으면 더 이상 볼 필요가 없지 않을 까?
-> DP로 방문 처리 하자

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setlimits(500*500)
# 세로 가로 길이
M, N = map(int, input().split())

mapping = [list(map(int, input().split())) for _ in range(M)]
# DP 방문 배열 방문 하지 않았으면 -1
DP = [[-1] * N for _ in range(M)]
di = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def DFS(x, y):
	# 도착지
    if x == M-1 and y == N-1:
        return 1
    # 이미 방문 했다면
    if DP[x][y] != -1:
        return DP[x][y]
    # 방문 경로 저장 변수
    cnt = 0
    # 네 방향 탐색
    for dx, dy in di:
        nx, ny = x + dx, y + dy
        if nx < 0 or ny < 0 or nx >=M or ny >= N: continue
        if mapping[x][y] <= mapping[nx][ny]: continue
        cnt += DFS(nx, ny)
    DP[x][y] = cnt
    return DP[x][y]
print(DFS(0, 0))