LeetCode 2684 Maximum Number of Moves in a Grid (Java)

http://leetcode.com/problems/maximum-number-of-moves-in-a-grid

 

class Solution {
    public int maxMoves(int[][] grid) {
    

        int ans=0;

        int c = grid[0].length;
        int r = grid.length;
        int dp[][] = new int[r][c];

        for (int j = c - 2; j >= 0; j--) {
            for (int i = 0; i < r; i++) {
                if (i - 1 >= 0 && j + 1 < c && grid[i][j] < grid[i - 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1] + 1);
                }
                if (grid[i][j] < grid[i][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
                }
                if (i + 1 < r && j + 1 < c && grid[i][j] < grid[i + 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j + 1] + 1);
                }
            }
        }

        for (int k = 0; k < r; k++) {
            ans = Math.max(ans, dp[k][0]);
        }

        return ans;
    }
}

1. 문제

m*n의 배열이 주어진다. 해당 배열의 왼쪽 끝에서 시작하여 이동하는데, 우상, 우, 우하의 방향으로 현재 위치의 값보다 큰 숫자로만 이동할 수 있다. 이 때 가능한 최대 움직임 수를 구하라.

2. 풀이

DP 문제이다. 종착점은 배열에 따라 다르지만, 시작점은 항상 일정하므로 우측 끝에서부터 역으로 이동하여 풀도록 하자.

        int c = grid[0].length;
        int r = grid.length;
        int dp[][] = new int[r][c];

우선 메모이제이션 배열을 선언한다. 정의는 다음과 같다.

• dp[i][j]: (i, j)에서 시작하여 조건에 맞춰 이동할 수 있는 최대 거리

        for (int j = c - 2; j >= 0; j--) {
            for (int i = 0; i < r; i++) {
                if (i - 1 >= 0 && j + 1 < c && grid[i][j] < grid[i - 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1] + 1);
                }
                if (grid[i][j] < grid[i][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
                }
                if (i + 1 < r && j + 1 < c && grid[i][j] < grid[i + 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j + 1] + 1);
                }
            }
        }

이후 좌측으로 가면서 계산한다. 문제의 조건을 역으로 탐색하면 좌상, 좌, 좌하로 현재 위치보다 작은 숫자의 경우에만 이동할 수 있다. 이에 따라 배열의 범위를 확인하면서 세 가지 케이스를 확인해준다.

        for (int k = 0; k < r; k++) {
            ans = Math.max(ans, dp[k][0]);
        }

        return ans;

이후 맨 좌측의 어디서 출발해야 최대 거리를 이동할 수 있는 지 확인, 그 거리를 리턴한다.