Python - 내리막 길 (1520) DP, DFS

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

1520번: 내리막 길

 

1. DP 배열을 -1로 채워 방문하지 않았던 것을 표시합니다.

2. 만약 현재 위치 DP 배열에 방문을 했었다면 DP 배열에 있는 값을 가지고 리턴 합니다.

 

 

import sys
dire = [[-1, 1, 0, 0], [0, 0, -1, 1]]
def DFS(x, y):
  # 끝에 도착했다면
    if x == len(downHill) - 1 and y == len(downHill[0]) - 1: 
        return 1
        
    # 현재 위치를 방문한 적 있었다면
    # 값을 가지고 return
    if DP[x][y] != -1:
        return DP[x][y]
    
    DP[x][y] = 0
    for d in range(4):
        nx = x + dire[0][d]
        ny = y + dire[1][d]
        if not (0 <= nx < len(downHill)) or not (0 <= ny < len(downHill[0])): continue
        if downHill[x][y] <= downHill[nx][ny] : continue
        DP[x][y] += DFS(nx, ny)
        
    # 4 방향을 봐도 더이상 탐색할 곳이 없다면 현재 위치 값을 가지고 return
    return DP[x][y]

n, m = map(int, sys.stdin.readline().strip().split())
DP = [[-1] * m for _ in range(n)]
downHill = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]
print(DFS(0, 0))