[백준 1520] 내리막길 (Python)

백준 1520 - 내리막길

코드

import sys
sys.setrecursionlimit(10 ** 8)

N, M = map(int, sys.stdin.readline().split())
W = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[-1] * (M) for _ in range(N)]
dp[N - 1][M - 1] = 1

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

    tmp = 0
    for d in dxy:
        nx, ny = x + d[0], y + d[1]
        if 0 <= nx < M and 0 <= ny < N and W[y][x] > W[ny][nx]:
            tmp += dfs(nx, ny, W, dp)
    dp[y][x] = tmp

    return dp[y][x]
print(dfs(0, 0, W, dp))
        

풀이

문제를 풀 때 역으로 생각하는 편이 접근하기 쉬웠다. 시작점이 아닌 도착점에서 가까운 점들부터 도착점에서 그 점으로 갈 수 있는 경우의 수를 채우도록 구현을 했다.

tmp = 0
    for d in dxy:
        nx, ny = x + d[0], y + d[1]
        if 0 <= nx < M and 0 <= ny < N and W[y][x] > W[ny][nx]:
            tmp += dfs(nx, ny, W, dp)
    dp[y][x] = tmp

시작점에서 dfs를 진행하되 dp배열에서 자신의 인덱스에 들어갈 값은 아래와 같이 상하좌우 중 지도에서 자신보다 작은 값의 dp배열의 값들의 합이 된다.

따라서 dp배열을 -1로 채워주고 도착점에만 1을 채운 뒤 dfs를 돌려주면 된다. 이때 0이 아닌 -1로 채워주는 이유는 dp배열의 실제 값이 0일 수도 있기 때문이다. 따라서 방문하지 않은 점과 혼동하지 않기 위해 나올 수 없는 값인 -1로 채워준다.

그리고 dfs를 진행할 때 dp배열에 -1이 아닌 값이 들어있으면 이미 도착점까지 탐색을 끝냈던 점이므로 바로 dp배열 내 값을 반환해준다. 즉 메모이제이션을 사용해준다.

피드백 환영합니다.
-끝-