boj.kr/1520 내리막 길 (gold3) 파이썬 풀이

dfs + dp

1. 그래프와 동일한 크기로 dp테이블을 -1으로 초기화

2. dfs 내부에서 dp 테이블에 저장된 좌표면 저장된 값을 반환

3. 맨 오른쪽 맨 아래 좌표이면 1을 반환

4. 2, 3에 해당하지 않으면 처음 방문하는 좌표이므로 dp 테이블에 0을 저장

5. 상하좌우 검사해 현재 좌표에 저장된 값보다 작으면 dfs에 해당좌표를 인자로 재귀호출한 결과를 dp 테이블에 저장

6. dfs에 전달된 좌표에 해당하는 dp테이블 값을 반환

 

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

import sys
sys.setrecursionlimit(10**9)

dy = (0, 0, 1, -1)
dx = (1, -1, 0, 0)
def dfs(y, x):
    if dp[y][x] != -1:
        return dp[y][x]
    if y == M-1 and x == N-1:
        return 1
    dp[y][x] = 0
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=ny<M and 0<=nx<N and graph[y][x] > graph[ny][nx]:
            dp[y][x] += dfs(ny, nx)
    return dp[y][x]

print(dfs(0, 0))

 

dp[y][x] 으로 graph[y][x]에서 graph[M-1][N-1] 좌표까지 가는 경로의 수를 저장한다.

dp 배열을 사용하지 않으면 시간초과가 발생한다.