Python - [백준]1520-내리막길

출처

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

문제

현재 위치의 높이보다 낮은 높이를 가진곳으로만 이동하여 목적지 까지 가는 경로의 수를 구하는 문제이다

접근 방법

DFS를 기본 개념으로 사용하지만 그것만 사용하게 된다면 무수히 많은 경우의 수를 낳기 때문에 불가능하다. 그래서 DP를 이용하여 연산횟수를 줄여주어야 한다.
DP를 사용하기 위한 조건인 전체 문제의 최적해가 부분 문제의 최적해로 나누어지는지를 살펴 보아야 한다.

이 문제를 시작점에서부터 도착점으로 가는 경로의 수를 구하는 문제에서, 임의의 점(x, y)에서 도착점 까지의 경우로 세분화 하여 구한다면, 그 어떤 경로로 (x, y)에 도착 하기만 해도 그 때부터의 경우의 수는 다시 구할 필요가 없다.

정리하자면, 도착 지점까지 가는 경우의 수는 도착 지점이 아닌 임의의 점들에서 도착지점까지 가는 경우의 수를 합한 것과 같다.

그렇다면, 어떻게 메모이제이션을 할 것이냐?

• DP 테이블을 -1로 초기화 하여 생성한다. 0이 아닌 -1인 이유는 방문여부(visted)를 알기 위하여 -1로 초기화 한다.
• 시작 지점에서 출발하여 만약 DP테이블이 갱신 되지 않은 -1인 임의의 점을 만난다면 해당 지점부터 도착지점 까지 갈 수 있는 경로의 수를 재귀적으로 업데이트 해준다.
• 만약 해당 지점의 DP테이블이 -1이 아닌 업데이트 되어있는 상태라면 더 진행 할 필요 없이, 그 지점이 부분 최적해가 되므로 그 지점의 DP테이블의 값을 바로 반환해준다.
• 종료 지점에 도착 한 경우, 1을 바로 반환해준다.

풀이

백준에 그대로 제출하면 Recursion Error가 발생한다. 문제 조건에 10억회라고 제한이 걸려있기 때문에 한계를 걸어주어야 (sys.setrecursionlimit(10 ** 9)) 에러가 발생 하지 않는다.

상하 좌우로 이동 할 수 있기 때문에 4번의 반복문을 통해 지도 범위 안이거나 높이가 낮다면 재귀호출을 하도록 구성하였다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

m, n = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(m)]
dp = [[-1]*n for i in range(m)]
dx = [0, 1, 0, -1]
dy = [1, 0 , -1, 0]

def is_range(x, y, now):
    return 0 <= x < m and 0 <= y < n and arr[x][y] < now

def solution(x, y):
    if x == m-1 and y == n-1:
        return 1
    if dp[x][y] == -1:
        dp[x][y] = 0
        for i in range(4):
            dr_x, dr_y = x + dx[i], y + dy[i]
            if is_range(dr_x, dr_y, arr[x][y]):
                dp[x][y] += solution(dr_x, dr_y)
    
    return dp[x][y]
        
    
print(solution(0, 0))

참고자료 : https://studyandwrite.tistory.com/387