[백준] 1520번: 내리막 길

문제

백준 - 1520번: 내리막 길

분석

지도가 주어지고 제일 왼쪽 위에서 제일 오른쪽 아래로 간다고 할 때, 그리고 높이가 낮은 지점으로만 이동할 수 있다고 할 때, 가능한 경로의 개수를 구하는 문제이다.

처음에 단순히 N과 M이 각각 500이하여서 단순 DFS를 사용하면 된다고 생각했다. 그런데 이것은 모든 가능한 경로를 구하기에 방문처리를 복원하는 방식으로 변경한다면 최악의 경우 4^(500X500)가 된다.

따라서 DP기법을 사용하여 연산량을 줄일 필요가 있다.
먼저, dp배열을 -1로 초기화하여 방문여부를 파악한다.
-1이 아니면 방문한 적이 있으므로 해당 값을 그대로 사용한다.
방문한 적이 없으면 cnt값에 dfs를 진행하고 return 받은 값을 축적한다.
dp[x][y] 값에 cnt를 저장하고 해당 dp값을 return한다.

dfs에서 return되면서 가짓수를 하나씩 늘려가기 때문에 도착한 곳이 목적지면 1을 반환한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**9)
n, m = map(int, input().split())
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]
dp = [[-1]*m for _ in range(n)]
dxs = [0,1,0,-1]
dys = [1,0,-1,0]

def in_range(x, y):
    return 0<=x<n and 0<=y<m

def dfs(x, y):
    if (x, y) == (n-1, m-1):
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    cnt = 0
    for dx, dy in zip(dxs, dys):
        nx, ny = x + dx, y + dy
        if in_range(nx, ny) and grid[x][y] > grid[nx][ny]:
            cnt += dfs(nx, ny)
    dp[x][y] = cnt
    return dp[x][y]
    
print(dfs(0, 0))

끝으로..

DFS에 DP를 결합한 문제를 처음 풀어봤는데, 비슷한 문제를 풀어보며 연습해야겠다.