[백준 2024/10/14] 1520번 내리막 길

1. 문제

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

 

2. 접근 방법

처음에는 2중 arr를 선언을 통해 해당 위치에서의 접근 route 개수를 구하려고 하였다.

따라서, max queue를 이용해서, 구현을 하였지만, 메모리 초과가 발생하였다.

 

이에, max_queue를 이용하지 않고 구현을 시작해야 했다. 즉, dfs + memoization을 이용한 구현을 통해서 메모리를 더 아낄 필요성이 있었다.

 

dp = [[-1] * m for _ in range(n)]

을 통해서 기본 값이 -1인 dp를 선언해 주었다.

이후, 특정 route가 dp[-1][-1]에 도달한다면, 1을 반환해 주어, 해당 목표 점에 도달이 성공하였음을 알려주었다.

 

따라서 i == n-1 and j == m-1 이라면 1을 반환해 주었다.

-1이 dp 값에 저장이 안되어 있다면, 해당 경로는 이미 계산이 완료된 상태이므로, 저장되어 있는 dp 값을 반환해 주었다.

또한 현재 위치에서 위, 아래, 왼쪽, 오른쪽을 탐색을 완료하였을 때, 범위 안에 있고 value가 줄어든다면 ways 에 해당 경로를 다시 탐색해 주었다.

 

3. 코드

import sys
sys.setrecursionlimit(10**8)


def dfs(dp, directions, i, j):
    if i == n-1 and j == m-1:
        return 1

    if dp[i][j] != -1:
        return dp[i][j]

    ways = 0
    for l, r in directions:
        if 0 <= i+l < n and 0 <= j+r < m and val[i][j] > val[i+l][j+r]:
            ways += dfs(dp, directions, i+l, j+r)

    dp[i][j] = ways
    return dp[i][j]

def get_routes(n, m):
    dp = [[-1] * m for _ in range(n)]

    dp[-1][-1] = 1
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    dfs(dp, directions, 0, 0)

    return dp[0][0]


if __name__ == "__main__":
    n, m = map(int, input().split())
    val = []
    for _ in range(n):
        val.append(list(map(int, input().split())))

    print(get_routes(n, m))