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

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

1520번: 내리막 길

dfs + dp로 목적지까지 도착할 수 있는지 검사한다

루프를 방지하기 위해 방문 확인 배열 c를 -1로 초기화하고 이동할 때마다 0으로 다시 설정해준다

 

1. 과정을 진행하면서 c에 이미 저장된 값이 0이면 목적지까지 갈 수 없으므로 0을 반환한다

2. 1 이상의 값이면 이전에 그만큼 방문 경로가 있으므로 해당 값을 반환해서 더해준다

3. -1이면 방문하지 않은 경로이므로 dfs + dp 수행 

import sys

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 c[x][y] != -1:
        return c[x][y]
    c[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 a[nx][ny] < a[x][y]:
                c[x][y] += dfs(nx, ny)
    return c[x][y]

m, n = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
c = [[-1]*n for _ in range(m)]
print(dfs(0, 0))