BOJ-1520 - Python

Y, X 크기의 정수로 이루어진 2차원 배열이 입력된다. 0, 0 위치에서 Y-1, X-1까지 해당 자리의 정수가 낮은 곳으로만 이동할 때, Y-1, X-1에 도착하는 경우의 수가 몇가지인 지 출력하는 문제. 첫 번째 풀이는 단순 다이내믹 프로그래밍 방법을 이용하여 풀었으나 먼저 계산된 곳이 있을 시 연산이 안되는 부분이 있어 각 방향마다 연산을 더 하도록 하지 않는 이상 안될 것 같아 방향을 틀었다. 두 번째 풀이는 -1로 선언된 배열을 만든 후 해당 배열을 이용하여 방문확인과 함께 이동방향의 값을 더하는 것을 재귀적으로 연산하여 풀었다.

# dire = [[1, 0],
#         [-1, 0],
#         [0, 1],
#         [0, -1]]
#
# Y, X = map(int, input().split())
# graph = [[] for _ in range(Y)]
# for i in range(Y): graph[i] = list(map(int, input().split()))
# dp = [[0 for _ in range(X)] for _ in range(Y)]
# dp[0][0] = 1
#
# for y in range(Y):
#     for x in range(X):
#         for ty, tx in dire:
#             ny = y + ty
#             nx = x + tx
#             if 0 <= ny < Y and 0 <= nx < X:
#                 if graph[ny][nx] < graph[y][x]:
#                     dp[ny][nx] += dp[y][x]
#                     print(y, x)
#
# for i in dp:
#     print(i)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def dfs(y, x):
    if Y-1 == y and X-1 == x:
        return 1

    if dp[y][x] == -1:
        dp[y][x] = 0
        for ty, tx in dire:
            ny, nx = y + ty, x + tx
            if 0 <= ny < Y and 0 <= nx < X:
                if graph[y][x] > graph[ny][nx]:
                    dp[y][x] += dfs(ny, nx)
    return dp[y][x]

dire = [[1, 0], [-1, 0], [0, 1], [0, -1]]
Y, X = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(Y)]
dp = [[-1 for _ in range(X)] for _ in range(Y)]

dfs(0, 0)
print(dp[0][0])