[프로그래머스] 등굣길

func solution(m: Int, n: Int, puddles: [[Int]]) -> Int {
    var grid: [[Int]] = Array(repeating: Array(repeating: 0, count: m + 1), count: m + 1)
    grid[1][1] = 1
    for puddle in puddles {
        grid[puddle[1]][puddle[0]] = -1
    }
    for i in 1...n {
        for j in 1...m {
            if grid[i][j] == -1 {
                grid[i][j] = 0
                continue
            }
            grid[i][j] += (grid[i - 1][j] + grid[i][j - 1]) % 1000000007
        }
    }
    return grid[n][m]
}

1. path 를 DFS 로 탐색. (경로의 개수를 구해야하기 때문에)
2. 격자에다가 현재까지 탐색한 이동값을 넣어줌 (같거나 작은 경우만 계속 탐색)
3. 탐색을 완료하면 값에 따라 cnt 갱신

minMoveCnt = 100000
pathCnt = 0
def solution(m, n, puddles):
    grid = [[ 0 for _ in range(m + 1)] for _ in range(n + 1)]
    moves = [(0,1), (1,0)]
    for puddle in puddles:
        grid[puddle[1]][puddle[0]] = -1
    def DFS(x,y, moveCnt):
        global minMoveCnt
        global pathCnt
        if (x,y) == (m,n):
            if moveCnt == minMoveCnt:
                pathCnt += 1
            elif moveCnt < minMoveCnt:
                minMoveCnt = moveCnt
                pathCnt = 1
            return
        for move in moves:
            dx = x + move[0]
            dy = y + move[1]
            if dx <= m and dy <= n:
                if grid[dy][dx] == 0 or moveCnt + 1 <= grid[dy][dx]:
                    grid[dy][dx] = moveCnt + 1
                    DFS(dx,dy, moveCnt + 1)

    DFS(1,1,0)
    return pathCnt