Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 체리 수확(Cherry Pickup) 문제 풀이 – 동적 계획법으로 최대 체리 수집하기

N×N 크기의 격자(grid)에 체리가 가득 차 있다고 가정해 보겠습니다. 각 칸에는 다음 세 가지 정수 중 하나가 들어 있습니다.

  • 0 – 빈 칸을 의미하며, 자유롭게 지나갈 수 있습니다.
  • 1 – 체리가 들어 있는 칸을 의미하며, 지나가면서 체리를 수확할 수 있습니다.
  • -1 – 가시(thorn)가 있는 칸을 의미하며, 지나갈 수 없어 길을 막습니다.

문제 규칙

다음 규칙에 따라 최대한 많은 체리를 수집해야 합니다.

  • (0, 0)에서 출발해 오른쪽 또는 아래 방향으로만 이동하며, 유효한 경로를 통해 (N-1, N-1)에 도착합니다.
  • (N-1, N-1)에 도착한 후에는 왼쪽 또는 위 방향으로만 이동해 다시 (0, 0)으로 돌아옵니다.
  • 체리가 있는 칸을 지나가면 해당 체리를 수확하며, 그 칸은 빈 칸(값 0)으로 바뀝니다.
  • (0, 0)과 (N-1, N-1) 사이에 유효한 경로가 존재하지 않으면 수확할 수 있는 체리는 없습니다.

예제 살펴보기

예를 들어 입력이 다음과 같다고 해봅시다.

01-1
10-1
111

이 경우 출력은 5입니다. (0, 0)에서 출발해 아래 → 아래 → 오른쪽 → 오른쪽 순서로 이동해 (2, 2)에 도착하면, 이 한 번의 여정에서 체리 4개를 수확하게 되고 격자는 다음과 같이 변합니다.

01-1
00-1
000

이후 왼쪽 → 위 → 위 → 왼쪽 순서로 이동해 (0, 0)으로 돌아오는 길에 체리 한 개를 추가로 수확합니다. 따라서 총 수확량은 5개가 됩니다.

접근 방법: 두 경로를 동시에 시뮬레이션

가는 길과 오는 길을 따로 계산하는 대신, 두 명의 사람이 (0, 0)에서 동시에 출발해 (N-1, N-1)까지 함께 이동한다고 생각하면 문제가 훨씬 단순해집니다. 두 위치 (r1, c1)과 (r2, c2)는 항상 같은 스텝 수를 유지하므로 r1 + c1 = r2 + c2라는 관계가 성립하고, 이를 이용해 r2 = r1 + c1 − c2로 계산할 수 있습니다. 덕분에 상태를 (r1, c1, c2) 세 값만으로 표현할 수 있어 메모이제이션(dp) 배열의 크기를 크게 줄일 수 있습니다.

두 사람이 같은 칸에 도착했다면 체리는 중복 없이 한 번만 더해집니다.

풀이 단계

  • 크기 2×2인 방향 배열 dir을 {{1, 0}, {0, 1}}로 정의합니다.
  • INF := 10^9로 설정합니다.
  • 크기 51 × 51 × 51인 dp 배열을 선언합니다.
  • solve(r1, c1, c2, grid) 함수를 정의합니다.
  • n := grid의 크기, r2 := r1 + c1 − c2, ret := 0으로 초기화합니다.
  • m := n이 0이 아니면 grid[0]의 크기, 아니면 0으로 설정합니다.
  • r1, c1, r2, c2 중 하나라도 범위를 벗어나면 -INF를 반환합니다.
  • grid[r1][c1] 또는 grid[r2][c2]가 -1(가시)이면 -INF를 반환합니다.
  • (r1, c1)이 목적지(n-1, m-1)와 같으면 grid[r1][c1]을 반환합니다.
  • dp[r1][c1][c2]가 이미 계산되어 있다면(-1이 아니라면) 그 값을 반환합니다.
  • ret에 grid[r1][c1]을 더합니다. 두 위치가 같지 않다면 ret에 grid[r2][c2]도 더합니다.
  • temp := -INF로 초기화한 뒤, k = 0부터 k < 2까지 반복하며 다음을 수행합니다.
    • temp := max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid))
    • temp := max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid))
  • dp[r1][c1][c2] = ret + temp를 반환합니다.
  • 메인 함수에서는 dp 배열을 -1로 채운 뒤, solve(0, 0, 0, grid)를 호출하고 결과와 0 중 큰 값을 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int dir[2][2] = {{1, 0}, {0, 1}};
const int INF = 1e9;
class Solution {
public:
    int dp[51][51][51];
    int solve(int r1, int c1, int c2, vector<vector<int>>& grid){
        int n = grid.size();
        int r2 = r1 + c1 - c2;
        int ret = 0;
        int m = n ? grid[0].size() : 0;
        if(r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || r2 >= n || c1 >= m || c2 >= m) return -INF;
        if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -INF;
        if(r1 == r2 && c1 == c2 && r1 == n - 1 && c1 == m - 1) return grid[r1][c1];
        if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
        ret += grid[r1][c1];
        if(r1 == r2 && c1 == c2){
        } else ret += grid[r2][c2];
        int temp = -INF;
        for(int k = 0; k < 2; k++){
            temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid));
            temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid));
        }
        return dp[r1][c1][c2] = ret + temp;
    }
    int cherryPickup(vector<vector<int>>& grid) {
        memset(dp, -1, sizeof(dp));
        int ret = solve(0, 0, 0, grid);
        return max(0, ret);
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
    cout << (ob.cherryPickup(v));
}

입력

{{0,1,-1},{1,0,-1},{1,1,1}}

출력

5

마무리

이 문제의 핵심은 왕복 여정을 두 명의 독립적인 이동자로 모델링하는 것입니다. 이렇게 하면 단순히 두 번 탐색하는 방식보다 훨씬 효율적으로 최적해를 찾을 수 있으며, 메모이제이션으로 중복 계산을 제거하면 O(N³)의 시간 복잡도 안에 문제를 해결할 수 있습니다.