[백준] 1520번 내리막길 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/1520

문제해결 아이디어

• 단순 dfs만으로는 시간초과가 난다.=> dp를 활용해서 시간복잡도를 줄여야 함.
• 목표지점 n-1, m-1에 도달하면 시작점에서 도착점까지 성공적으로 방문한 한 가지 경우가 되므로 1을 리턴해주고, 해당 값을 지금까지 걸어온 경로에 모두 더해준다.
• 만약에 현재 방문중인 경로를 이미 다른 경로가 방문하여 -1이 아닌 다른 값으로 업데이트 되어있다면 (0 or n으로) 더 이상의 탐색은 진행하지 않고 해당 값을 업데이트 해준다.

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int, input().split())))

dp = [[-1] * m for _ in range(n)]

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


def dfs(x, y):
    if x == n - 1 and y == m - 1:    
        return 1

    if dp[x][y] != -1:
        return dp[x][y]

    way = 0

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

        if 0 <= nx < n and 0 <= ny < m and graph[x][y] > graph[nx][ny]:
            way += dfs(nx, ny)

    dp[x][y] = way

    return dp[x][y]


print(dfs(0, 0))