[BOJ][Python] 백준 1520번: 내리막 길

1일 1PS 61일차!

📚 문제

---

골드 3 내리막 길

💡 풀이 과정

---

• DFS 와 DP 를 같이 사용한다.
• 해당 칸에 도착할 수 있는 방법의 수를 DP 에 저장한다. 도착지를 1로 설정해 놓으면 DP[0][0] 이 도착지까지 갈 수 있는 방법의 수이다.

📌포인트

---

• DFS 를 진행할 때 가장 신경쓰였던 부분은 DP[5][5] 를 계산할 때 만약 DP[6][5] 가 최신화 되어있지 않다면? 이었다.
  • 하지만 DFS 에서 DP[5][5] 를 계산하기 위해서는 5 이상 모든 영역이 계산이 끝나야 DP[5][5] 가 계산될 수 있으므로 순서가 어긋날 고려는 하지 않아도 된다!!

💻 코드

---

import sys

input = sys.stdin.readline

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

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
dp = [[-1] * M for _ in range(N)]
dp[N - 1][M - 1] = 1


def dfs(x, y):
    if dp[x][y] != -1:
        return dp[x][y]

    temp = 0
    for d in range(4):
        nx, ny = x + dx[d], y + dy[d]

        if 0 <= nx < N and 0 <= ny < M:
            if board[nx][ny] < board[x][y]:
                temp += dfs(nx, ny)

    dp[x][y] = temp
    return dp[x][y]


print(dfs(0, 0))