576. Out of Boundary Paths

• 크기가 m x n 인 공간이 존재할 때 특정 위치 (startRow, startColumn)에서 최대 maxMove 회 만큼 움직였을 때 해당 공간에서 벗어날 수 있는 경우의 수를 구하는 문제.

• 우선 최대 움직일 수 있는 횟수가 0인 경우는 답이 없는 것이 명확하기 때문에 제외한다.

• 현재 위치를 기준으로 동, 서, 남, 북 각 방향으로 탐색하면서 공간 외부로 도달하는 경우의 수를 찾는다.
• 서 (-1, 0), 동 (1, 0), 북 (0, -1), 남 (0, 1) 각 방향에 대한 움직임을 미리 배열 delta에 담아둔다.
• 공간에서 벗어난 경우에는 유효한 결과이므로 값을 1로 한다.
• 더 이상 움직일 수 없는 경우 move == 0에는 값을 0으로 한다.
• 각 방향으로 시도하여 공간에서 벗어난 경우의 수를 모두 더한다.

• 현재까지 움직인 횟수 move + 현재 위치 (i, j) 별로 공간 외부에 도달하는 경우의 수는 매번 계산해도 동일하게 나오기 때문에 memoization을 활용한다.
• 3차원 배열 dp을 생성하여 현재까지 움직인 횟수 move - 1, x 좌표 i, y 좌표 j 별로 공간 외부에 도달하는 경우의 수를 저장한다.
• 이미 저장된 경우의 수 dp[move - 1][i][j]가 있다면 계산하지 않고 바로 값을 꺼내서 돌려준다.

class Solution {
    final int MOD = 1_000_000_000 + 7;
    final int[][] delta = new int[][] {
        {-1,  0},
        { 1,  0},
        { 0, -1},
        { 0,  1},
    };
    
    int traverse(int[][][] dp, int i, int j, int move) {
        if (i < 0 || j < 0 || i >= dp[0].length || j >= dp[0][0].length) {
            return 1;
        } else if (move == 0) {
            return 0;
        } else if (dp[move - 1][i][j] != -1) {
            return dp[move - 1][i][j];
        }
        int result = 0;
        for (int[] d : delta) {
            result = (result + traverse(dp, i + d[0], j + d[1], move - 1)) % MOD;
        }
        return dp[move - 1][i][j] = result;
    }
    
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0) {
            return 0;
        }
        int[][][] dp = new int[maxMove][m][n];
        for (int[][] sub : dp) {
            for (int[] subsub : sub) {
                Arrays.fill(subsub, -1);
            }
        }
        return traverse(dp, startRow, startColumn, maxMove);
    }
}

• dp 초기화 부분에서 stream을 활용하면 더 코드가 깔끔해지기는 하지만 성능 차이가 꽤 있어서 for loop 방식을 사용하는게 더 낫다.

class Solution {
    ... omitted ..,
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0) {
            return 0;
        }
        int[][][] dp = new int[maxMove][m][n];
        Arrays.stream(dp)
            .flatMap(Arrays::stream)
            .forEach((a) -> Arrays.fill(a, -1));
        return traverse(dp, startRow, startColumn, maxMove);
    }
}