프로그래머스 level3 등굣길 (python)

Problem

https://school.programmers.co.kr/learn/courses/30/lessons/42898#

Solution

def solution(m, n, puddles):
    _map = [[0] * m for _ in range(n)]
    
    def dp(a, b):
        # 시작 점
        if a == 0 and b == 0:
            _map[a][b] = 1
            return 1
        # 지도 밖 & 웅덩이
        if (a < 0 or b < 0) or [b+1, a+1] in puddles:
            return 0
        
        if _map[a][b] != 0:
            return _map[a][b]
        _map[a][b] = dp(a, b-1) + dp(a-1, b)
        return _map[a][b]
    
    return dp(n-1, m-1) % 1000000007

최단거리를 이동하기 위해서는 오른쪽 또는 아래로만 이동할 수 있다. 따라서 (a, b)에 도착하기 위해서는 (a-1, b) 이나 (a, b-1)에서 접근해야 한다. 지도 밖이나 물 웅덩이는 0, 시작점은 1이라 세팅하고 DP를 이용하며 문제를 해결하였다.