프로그래머스 / 등굣길 / python

def solution(m, n, puddles):
    answer = 0
    direction = [[1,0], [0,1]]
    
    def dfs(x, y, deph):
        if x == n-1 and y == m-1:
            dp[x][y] = 1
            return
        
        if dp[x][y] != -1:
            return
        
        dp[x][y] = 0
        
        for d in direction:
            nx, ny = x+d[0], y+d[1]
            if 0 <= nx < n and 0 <= ny < m and not maps[nx][ny]:
                dfs(nx,ny, deph +1)
                dp[x][y] += dp[nx][ny]
    
    maps = [[0] * m for _ in range(n)]
    dp = [[-1] * m for _ in range(n)]
    
    for puddle in puddles:
        maps[puddle[1] -1][puddle[0] -1] = 1
    dfs(0,0,0)

    return dp[0][0] % 1000000007

dfs와 dp로 해결한 문제

처음에 n*m 크기의 list를 0의 초기 값을 갖도록 만들어 준 후 물 운덩이에 해당하는 부분을 1로 둬서 나중에 해당 좌표는 탐색하지 않도록 한다.

그 다음 dfs로 갈 수 있는 경로를 탐색한다.
이 문제에서 dp는 top down 방법이다 끝에부터 시작해서 시작지점까지 올 수 있는 경우를 저장하면서 재귀해 온다.

dp를 통해 -1이 아닌 경우 즉 이미 계산이 진행됐던 곳이라면 그 부분에 대해 재귀를 진행하지 않음으로서 연산시간을 절약할 수 있다.

이게 가능한 이유는 움직일 수 있는 방향이 오른쪽과 아래쪽으로 이동가능 하기 때문에 이동한 후 길이 막혀 다시 돌아올 일이 없기 때문이다.

---

백준에 매우 유사한 문제가 있어서 쉽게 해결할 수 있었다.
-> https://www.acmicpc.net/problem/1520