https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으
www.acmicpc.net
DFS를 통해 구현하 되 메모이제이션을 하지 않는다면 시간초과가 날 것입니다.
특정 좌표에서 가고자 하는 좌표까지 갈 수 있는 경우의 수를 계속해서 배열에 저장해준다면, 다음 번에 그 좌표를 만났을 때 재귀를 돌지 않고 바로 값을 받을 수 있게 되므로 시간을 많이 단축 시킬 수 있습니다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
my_map = []
row, column = map(int, input().split())
for _ in range(row):
my_map.append(list(map(int, input().split())))
cache = [[-1 for _ in range(column)] for _ in range(row)]
def dfs(y, x):
if y == row-1 and x == column-1:
return 1
if cache[y][x] != -1:
return cache[y][x]
cache[y][x] = 0
for ii in range(4):
ny = y + dy[ii]
nx = x + dx[ii]
if not 0<=nx<column or not 0<=ny<row:
continue
if my_map[ny][nx] >= my_map[y][x]:
continue
cache[y][x] += dfs(ny, nx)
return cache[y][x]
print(dfs(0, 0))