백준 #1520 #Python

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

이 문제는 정석적인 DP문제라고 볼 수 있습니다.

DP문제는 가장 작은 독립적인 단위를 찾아 순회가 없는 단방향 그래프를 만드는 것이라고 생각하면 편합니다.

이 문제에선 (r, c) 에서 도착지점까지 가는 방법의 수가 독립적인 단위입니다.
이전에 어떤경로로 (r, c)까지 왔던 (r, c)에서 도착지점까지 갈 수 있는 방법의 수는 변하지 않습니다.

이를 F(r, c)이라고 한다면,
F(r, c) = F(r+1, c) + F(r, c+1) + F(r-1, c) + F(r, c-1) 이 됩니다.

또한, 큰 숫자에서 작은 숫자로만 이동이 가능하다는 조건이 순회가 없는 단방향 그래프를 만들어줍니다.

import sys
sys.setrecursionlimit(250000)
input = sys.stdin.readline

d = [(0,1), (1,0), (0,-1), (-1,0)]

def makeIt(row, col):

    if row==n and col==m: return 1              # 도착지점에 도착했으면 1을 리턴

    if dp[row][col] >= 0: return dp[row][col]   # 이미 방문한 노드라면 해당 dp리턴
    
    cnt = 0
    for i in range(4):
        nr, nc = row+d[i][0], col+d[i][1]
        if board[row][col] > board[nr][nc]:
            cnt += makeIt(nr, nc)               # 도착지점까지 갈 수 있는 방법 카운트

    dp[row][col] = cnt                          # dp에 입력
    return dp[row][col]
    

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

board = [[10001]*(m+2)] + [[10001]+list(map(int, input().split()))+[10001] for _ in range(n)] + [[10001]*(m+2)]
dp = [[-1]*(m+2) for _ in range(n+2)]
print(makeIt(1, 1))