🛠 문제
👩🏻💻 해결 방법
dfs/bfs로 풀어야겠다는 생각은 했지만 dp랑 어떻게 연결해서 풀어야할지 생각하기가 조금 어려웠던 문제다
dfs 함수에서 현재 좌표를 기준으로 상하좌우 확인했을 때, 이동이 가능하면 dfs 함수를 다시 불러와서 dp에 계속 값을 저장해주는 방식으로 풀 수 있었다
dfs 함수에서는 맨 마지막까지 도달하면 return 1, 중간에 이미 도달한 적이 있다면(-1이 아니라면) return dp[x][y], 도달할 수 없다면 return 0을 해주었다
소스 코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
if x == m-1 and y == n-1:
return 1
if dp[x][y] != -1:
return dp[x][y]
dp[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<m and 0<=ny<n:
if graph[x][y] > graph[nx][ny]:
dp[x][y] += dfs(nx, ny)
return dp[x][y]
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]
print(dfs(0, 0))