1463. Cherry Pickup II

프로그래밍 문제 해결에서 "체리 픽업 II"는 두 로봇이 체리를 수집하는 과정을 통해 최적화 문제를 해결하는 독특한 도전입니다. 이 문제는 로봇이 주어진 그리드 위를 이동하면서 체리를 수집하되, 특정 규칙을 따라야 한다는 설정을 가지고 있습니다.

---

문제 이해 🤔

주어진 rows x cols 크기의 그리드에서, grid[i][j]는 (i, j) 셀에서 수집할 수 있는 체리의 수를 나타냅니다. 두 로봇은 각각 그리드의 상단 왼쪽 모서리(0, 0)와 상단 오른쪽 모서리(0, cols - 1)에 위치하며, 다음 규칙을 따라 움직입니다:

1. 셀 (i, j)에서 로봇은 셀 (i + 1, j - 1), (i + 1, j), 또는 (i + 1, j + 1)로 이동할 수 있습니다.
2. 로봇이 셀을 지나가면, 그 셀의 모든 체리를 수집하고, 해당 셀은 빈 셀이 됩니다.
3. 두 로봇이 같은 셀에 도착할 경우, 체리는 한 로봇만 수집할 수 있습니다.
4. 로봇은 그리드 밖으로 이동할 수 없습니다.
5. 두 로봇 모두 그리드의 하단 행에 도달해야 합니다.

이 문제의 목표는 두 로봇이 수집할 수 있는 체리의 최대 수를 반환하는 것입니다.

예시 😮

예시 #1

• 입력: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
• 출력: 24 설명: 로봇 #1과 #2의 경로는 각각 녹색과 파란색으로 설명되어 있습니다.
• 로봇 #1이 수집한 체리, (3 + 2 + 5 + 2) = 12.
• 로봇 #2가 수집한 체리, (1 + 5 + 5 + 1) = 12.
• 체리의 총 합: 12 + 12 = 24.

예시 #2

• 입력: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
• 출력: 28 설명: 로봇 #1과 #2의 경로는 각각 녹색과 파란색으로 설명되어 있습니다.
• 로봇 #1이 수집한 체리, (1 + 9 + 5 + 2) = 17.
• 로봇 #2가 수집한 체리, (1 + 3 + 4 + 3) = 11.
• 체리의 총 합: 17 + 11 = 28.

해결 전략 📝

이 문제를 해결하기 위해서는 먼저 각 단계에서의 최적의 선택을 결정할 수 있는 동적 프로그래밍 방식을 고려해야 합니다. 각 로봇의 위치에 따라 가능한 모든 이동 경로를 고려하고, 각 단계에서 최적의 수집량을 갱신해 나가는 방식을 사용합니다.

1. 동적 프로그래밍 테이블 정의

각 단계에서, 우리는 두 로봇이 선택할 수 있는 모든 이동 경로를 고려합니다. 로봇은 현재 위치에서 좌측 대각선 하단(c-1), 바로 아래(c), 우측 대각선 하단(c+1)으로 이동할 수 있습니다. 이 중에서, 두 로봇이 같은 셀에 도착하게 되면 체리는 한 번만 수집되므로, 이 경우의 수집량을 조정해야 합니다. 각각의 가능한 이동 조합에 대해, 우리는 해당 이동이 가져올 수 있는 최대 체리 수를 계산하고, 이 중 최대값을 현재 위치의 최적 해로 선택합니다.

2. 최적의 이동 경로 계산

각 단계에서, 우리는 두 로봇이 선택할 수 있는 모든 이동 경로를 고려합니다. 로봇은 현재 위치에서 좌측 대각선 하단(c-1), 바로 아래(c), 우측 대각선 하단(c+1)으로 이동할 수 있습니다. 이 중에서, 두 로봇이 같은 셀에 도착하게 되면 체리는 한 번만 수집되므로, 이 경우의 수집량을 조정해야 합니다. 각각의 가능한 이동 조합에 대해, 우리는 해당 이동이 가져올 수 있는 최대 체리 수를 계산하고, 이 중 최대값을 현재 위치의 최적 해로 선택합니다.

3. 최종 결과 도출

모든 행을 순회한 후, 우리는 dp 배열의 마지막 행, 즉 dp[마지막 행][*][*]에 저장된 값들 중에서 최댓값을 찾습니다. 이 값은 두 로봇이 그리드를 통해 이동하면서 수집할 수 있는 체리의 최대 총량을 나타냅니다. 최종적으로, 이 최댓값이 문제의 해답이 됩니다.

구현 코드 🚀

public class CherryPickupII {
    public int cherryPickup(int[][] grid) {
    int R = grid.length, C = grid[0].length;
    int[][][] dp = new int[R][C][C]; // 1. 동적 프로그래밍 테이블 정의

    for (int[][] layer : dp) {
        for (int[] row : layer) {
            Arrays.fill(row, -1); // 초기값을 -1로 설정하여 아직 계산되지 않음을 표시
        }
    }

    return dfs(grid, dp, 0, 0, C - 1); // 첫 번째 위치에서 탐색 시작
}

private int dfs(int[][] grid, int[][][] dp, int r, int c1, int c2) {
    int R = grid.length, C = grid[0].length;
    if (c1 < 0 || c2 < 0 || c1 >= C || c2 >= C) return 0; // 범위를 벗어나는 경우 0 반환
    if (dp[r][c1][c2] != -1) return dp[r][c1][c2]; // 이미 계산된 경우 해당 값을 반환

    int result = grid[r][c1]; // 현재 위치에서 체리 수집
    if (c1 != c2) result += grid[r][c2]; // 두 로봇이 다른 셀에 있으면, 두 번째 로봇의 체리도 추가

    // 2. 최적의 이동 경로 계산: 다음 행으로 이동하는 모든 경우를 고려
    if (r < R - 1) {
        int max = 0;
        for (int newC1 = c1 - 1; newC1 <= c1 + 1; newC1++) {
            for (int newC2 = c2 - 1; newC2 <= c2 + 1; newC2++) {
                max = Math.max(max, dfs(grid, dp, r + 1, newC1, newC2)); // 모든 가능한 이동에 대해 최대 체리 수를 계산
            }
        }
        result += max; // 최대 체리 수를 현재 결과에 추가
    }

    dp[r][c1][c2] = result; // 계산된 결과를 저장
    return result; // 현재 위치에서의 최대 체리 수를 반환
}

    public static void main(String[] args) {
        CherryPickupII solution = new CherryPickupII();
        int[][] grid = {
            {0,8,7,10,9,10,0,9,6},
            {8,7,10,8,7,4,9,6,10},
            {8,1,1,5,1,5,5,1,2},
            {9,4,10,8,8,1,9,5,0},
            {4,3,6,10,9,2,4,8,10},
            {7,3,2,8,3,3,5,9,8},
            {1,2,6,5,6,2,0,10,0}
        };
        int result = solution.cherryPickup(grid);
        System.out.println(result); // 출력: 최대로 수집할 수 있는 체리의 수
    }
}

이 문제의 핵심은 각 단계에서 최적의 선택을 결정하고, 그 선택들을 통해 최종적으로 최대의 결과를 도출하는 것입니다. 동적 프로그래밍을 통해 복잡한 문제를 단순화하고 효율적으로 해결할 수 있음을 보여줍니다.

마무리 🌟

"체리 픽업 II" 문제는 동적 프로그래밍 기술을 활용하여 복잡한 최적화 문제를 해결하는 데 있어 좋은 연습이 됩니다. 이 문제를 통해 학습된 기술은 다양한 알고리즘 문제 해결에 적용될 수 있습니다. Happy coding! 👩‍💻👨‍💻