[백준] 1520번 내리막길 - 파이썬 / DFS

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

import sys
sys.setrecursionlimit(100000)
M,N = map(int,sys.stdin.readline().split())
N,M = M,N # 편하게 보기 위해 M,N 스왑
graph = []

for i in range(N):
    temt = list(map(int,sys.stdin.readline().split()))
    graph.append(temt)

visited = [ [0] *M for _ in range(N)]

cnt=0

def dfs(x,y):
    global cnt
    global visited
    if x == N - 1 and y == M - 1: # 도착점에서 dfs를 하면 방문리스트를 초기화해주고 종료
        visited = [[0] * M for _ in range(N)]
        return

    visited[x][y] = True
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]

    for i in range(4):

        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<N and 0<=ny<M and visited[nx][ny]==0 and graph[nx][ny]<graph[x][y]:
            if nx == N-1 and ny ==M-1: # 다음 지점이 도착점일때
                cnt+=1 # cnt 1 올린다
                dfs(nx, ny)
            else:
                dfs(nx,ny)

dfs(0,0)

if N==1 and M==1: # 1칸일때 조건 추가
    print(1)
else:
    print(cnt)

DFS로 풀었는데 시간 초과가 뜬다.

문제를 다시보니 DP 개념이 필요한 문제라서 DP를 공부하고 다시 풀어야 겠다.