🟩 [백준] [Python] [Gold3] 1520번_내리막 길

문제

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

1520번: 내리막 길

풀이

# 백준 1520번 문제 - 내리막 길
from collections import deque
dx, dy = [0,0,-1,1], [1,-1,0,0]
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1]*n for _ in range(m)]
cnt = 0

def dfs(x, y):
    if x == m-1 and y == n-1:
        return 1
    if dp[x][y] == -1:
        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]

print(dfs(0,0))

맨 처음 단순히 DFS 를 사용했는데 이렇게 되면 500*500 의 재귀이기 때문에 시간초과가 난다. 

따라서 방문했던 곳은 다시 처리하지 않아야 하는데 그것을 dp테이블을 만들어 해결하였다.