코드

1. 첫 풀이

import sys

sys.setrecursionlimit(10**8)

input = sys.stdin.readline
N,M = map(int,input().split(" "))

graph = [list(map(int,input().split(" "))) for _ in range(N)]
#visited = [[False]*M for _ in range(N)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]


cnt = 0 
def dfs(x,y):
    
    global cnt

    if x==N-1 and y==M-1:
        cnt += 1
        return 

    # if visited[x][y] == False:
    #     visited[x][y] = True

    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]

        if 0<=nx<N and 0<=ny<M and graph[x][y]>graph[nx][ny]: #visited[nx][ny]==False and
            dfs(nx,ny)
            # visited[nx][ny] = False


dfs(0,0)
print(cnt)

• 이런 식으로 갈 수 있는 경우를 모두 끝까지 확인하였다.
• 시간초과 발생.

2. 해결 코드

import sys

sys.setrecursionlimit(10**9)

input = sys.stdin.readline
N,M = map(int,input().split(" "))

graph = [list(map(int,input().split(" "))) for _ in range(N)]
visited = [[-1]*M for _ in range(N)]

dx = [-1,1,0,0]
dy = [0,0,-1,1]


cnt = 0 
def dfs(x,y):
    
    global cnt

    if x==N-1 and y==M-1:

        return 1
    if visited[x][y] == -1:
        visited[x][y] = 0

        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]

            if 0<=nx<N and 0<=ny<M and graph[x][y]>graph[nx][ny]: #visited[nx][ny]==False and
                visited[x][y] += dfs(nx,ny)
    
    return visited[x][y]


# dfs(0,0)
print(dfs(0,0))

• visited가 -1이라면 방문하지 않은 곳.
• 만약 해당 지점의 visited 테이블이 -1이 아닌 업데이트 되어있는 상태라면 더 진행 할 필요 없이, 그 지점이 부분 최적해가 되므로 그 지점의 visited 테이블의 값을 바로 반환해준다.