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

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

1520번: 내리막 길

 

import sys

sys.setrecursionlimit(200000)
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dfs(x, y):
    # 이미 방문한 적이 있을 경우
    if dp[x][y] != -1:
        return dp[x][y]

    # Base case
    if x == M-1 and y == N-1:
        return 1

    # Recursive case
    dp[x][y] = 0

    for i in range(4):
        nextX, nextY = x + dx[i], y + dy[i]

        if 0 <= nextX <= M-1 and 0 <= nextY <= N-1:
            if nums[x][y] > nums[nextX][nextY]:
                dp[x][y] += dfs(nextX, nextY)

    return dp[x][y]


if __name__ == '__main__':
    M, N = map(int, input().split())
    nums = [list(map(int, input().split())) for _ in range(M)]

    dp = [[-1]*N for _ in range(M)]
    print(dfs(0, 0))

 

DFS + DP로 풀었다.

DP[x][y]는 (x, y)에서 도달할 수 있는 경로이다. 즉, 우리는 DP[0][0]을 위해 코드를 작성한다.

DP는 모두 -1로 초기화하며, -1의 의미는 아직 방문하지 않은 것이다.

탐색 함수를 짤 때, 이것을 기준으로 방문한 적이 있을 경우에는 네 방향에 대한 탐색을 하는 것이 아니라, dp를 반환해준다.

아무튼, DFS의 구조가 꽤 간단하다. Base case는 x, y가 우측 하단인 경우이다.

그리고 Recursive case는, 내리막 길이라는 조건에 따라, 현재 좌표(x, y)에 대해 탐색을 해준다. 각 방향에 대한 경로의 경우의 수를 모아서 리턴해주는 식이다. 이렇게 하면 DP[0][0]이 우리가 원하는 값이 나온다.

 

여담이지만, 백준 온라인 저지에서 200문제를 해결하게 되었다.