[LeetCode] 576. Out of Boundary Paths

😎풀이

1. memo를 통해 현재 좌표에서 남은 걸음 수를 기반으로 바운더리를 벗어날 수 있는 경우의 수 캐싱
2. 깊이 우선 탐색 수행
   2-1. 좌표를 벗어날 경우 하나의 경우의 수로 취급
   2-2. 남은 걸음이 부족할 경우 불가능한 경우로 취급
   2-3. 네 방향을 탐색하며, 현재 셀에서 이동 가능한 캐싱된 경우의 수 탐색
   2-4. 현재 상태를 캐싱하며 벗어날 수 있는 경우의 수 반환
3. 현 위치에서 최대 걸음 수를 기반으로 벗어날 수 있는 경우의 수 반환

function findPaths(m: number, n: number, maxMove: number, startRow: number, startColumn: number): number {
    const MOD = 1e9 + 7
    const memo = Array.from({ length: m }, () => Array.from({ length: n }, () => Array(maxMove + 1).fill(-1)))
    function dfs(y: number, x: number, move: number) {
        if(y < 0 || y >= m || x < 0 || x >= n) return 1
        if(move === 0) return 0
        if(memo[y][x][move] !== -1) return memo[y][x][move]
        let res = 0
        const direct = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        for(const [dy, dx] of direct) {
            res = (res + dfs(y + dy, x + dx, move - 1)) % MOD
        }
        return memo[y][x][move] = res
    }
    return dfs(startRow, startColumn, maxMove)
};