[백준 C++] 17130번 토끼가 정보섬에 올라온 이유

17130번: 토끼가 정보섬에 올라온 이유

문제 요약

문제

토끼가 정보섬에 올라왔다! 정보섬은 N행 M열의 격자로 나타낼 수 있으며, 어째서인지 여기저기에 당근이 떨어져 있다. 방금 토끼 한 마리가 정보섬 정문으로 들어왔다. 토끼의 왼쪽에선 사나운 늑대가 쫓아오고 있어서, 토끼는 →, ↘, ↗ 방향으로만 이동한다. 토끼는 나가는 길에 최대한 많은 당근을 줍고싶다. 정문은 늑대 때문에 위험하므로 쪽문으로 나가야 하며, 토끼가 당근을 줍기 위해서는 그 당근이 있는 위치를 지나야 한다. 토끼가 어떤 쪽문에 도착했을때 반드시 그 문으로 탈출할 필요는 없으며, 더 움직여서 다른 쪽문으로 탈출해도 된다. 토끼는 얼마나 많은 당근을 주워갈 수 있을까? 토끼의 이동을 명확하게 정의하면 다음과 같다. 격자의 r행 c열 위치를 (r, c)라고 하자. 토끼의 현재위치가 (r, c)일때, 한 번의 이동으로 도착할 수 있는 위치는 (r+1, c+1), (r, c+1), (r-1, c+1)의 3가지다. 벽이나 격자의 밖으로는 이동할 수 없다.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫 줄에 격자의 크기 N과 M이 주어진다. 그 다음 줄부터 격자의 상태가 N개의 줄에 걸쳐 주어진다. ‘.’은 빈 공간을, ‘#’은 벽을, ‘R’은 토끼를, ‘C’는 당근을, ‘O’는 정보섬 쪽문을 나타낸다. ‘R’은 반드시 하나만 주어지며, ‘O’는 없거나 여러 개일 수 있다.
• 출력: 토끼가 정보섬을 빠져나가면서 얻을 수 있는 당근의 최대 개수를 출력한다. 정보섬에서 빠져나갈 수 없는 경우에는 -1을 출력한다. ``` 예제1

입력 3 5 RC#OO .#CCC ..O.. 출력 3

## 풀이
동적 계획법(DP)으로 풀 수 있는 문제다.
우선 모든 칸을 이동할 수 없음을 뜻하는 -1로 초기화해두고, 시작 지점인 'R'은 이동 가능하다는 의미로 0으로 설정해 시작한다.
이후 오른쪽 위, 오른쪽, 오른쪽 아래 방향으로만 이동할 수 있기 때문에(오른쪽 방향으로만 이동 가능), 해당 방향에서 올 수 있는 값 중 최댓값을 취해 현재 칸의 값을 업데이트해 나간다.
- C(당근)일 경우는 당근을 먹으므로 +1을 더한 값을 사용해 max를 비교해 갱신하면 되고,
- .일 경우는 단순히 이동만 가능하므로 기존 값들과의 max를 비교해서 갱신하면 된다.
- O는 목적지 후보이기 때문에 .와 똑같이 처리하되, 최종적으로 이 칸들 중 가장 큰 값을 따로 변수에 저장해 정답으로 사용한다.
- #은 벽이므로 무시하고 건너뛰면 된다.
이렇게 DP 테이블을 오른쪽으로 차례대로 갱신해가며 끝까지 도달했을 때, 목적지 후보들 중 가장 큰 값을 출력하면 된다.

## 어려웠던 점
평소 풀던 방향이 아닌 x축으로 이동하여 조금 헷갈렸다. 입력을 i와 j를 바꿔서 받는게 오히려 더 쉬웠을수도 있다고 생각한다.

## 배운 점 / 느낀 점
dp를 좀더 생각하면서 짤 수 있었다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<vector<char>> info_island;
vector<vector<int>> dp;
int carrot;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    info_island = vector<vector<char>>(n, vector<char>(m));
    carrot = -1;
    dp = vector<vector<int>>(n, vector<int>(m, -1));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> info_island[i][j];
        }
    }
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            if(info_island[i][j] == 'R'){
                if(j == m-1){
                    break;
                }
                dp[i][j+1] = 0;
                if(i!=0){
                    dp[i-1][j+1] = 0;
                }
                if(i!=n-1){
                    dp[i+1][j+1] = 0;
                }
            }
            if(dp[i][j] != -1){
                if(info_island[i][j] == '.'){
                    if(j == m-1){
                        continue;
                    }
                    dp[i][j+1] = max(dp[i][j], dp[i][j+1]);
                    if(i!=0){
                        dp[i-1][j+1] = max(dp[i][j], dp[i-1][j+1]);
                    }
                    if(i!=n-1){
                        dp[i+1][j+1] = max(dp[i][j], dp[i+1][j+1]);
                    }
                }
                else if(info_island[i][j] == 'C'){
                    if(j == m-1){
                        continue;
                    }
                    dp[i][j+1] = max(dp[i][j]+1, dp[i][j+1]);
                    if(i!=0){
                        dp[i-1][j+1] = max(dp[i][j]+1, dp[i-1][j+1]);
                    }
                    if(i!=n-1){
                        dp[i+1][j+1] = max(dp[i][j]+1, dp[i+1][j+1]);
                    }
                }
                else if(info_island[i][j] == 'O'){
                    carrot = max(carrot, dp[i][j]);
                    if(j == m-1){
                        continue;
                    }
                    dp[i][j+1] = max(dp[i][j], dp[i][j+1]);
                    if(i!=0){
                        dp[i-1][j+1] = max(dp[i][j], dp[i-1][j+1]);
                    }
                    if(i!=n-1){
                        dp[i+1][j+1] = max(dp[i][j], dp[i+1][j+1]);
                    }
                }
            }
        }
    }
    cout << carrot;
    return 0;
}