백준 17130번. 토끼가 정보섬에 올라온 이유(c++) / DP

DP가 아닌, BFS로도 풀 수 있는 문제이다.

행과 열의 값이 최대 1000이기 때문에 무리 없이 풀 수 있지만, DP로 풀기에 최적화된 문제라고 생각한다.

 

토끼가 →, ↘, ↗ 방향으로만 이동할 수 있기 때문에 현재 위치에서 그 전의 지점에서 올 수 있는 경로를 파악하여 dp값을 계속적으로 3지점의 최대값으로 갱신해주는 식으로 구현했다.

 

// 토끼가 정보섬에 올라온 이유
#include <cstring>
#include <iostream>
using namespace std;
 
int n, m, startX, startY;
string s;
int dp[1001][1001] = {0, };
char map[1001][1001];
int ans = 0;
bool check = false;
 
void rabbitMove()
{
    for(int j=startY; j<m; j++){
        for(int i=0; i<n; i++){
            if(map[i][j]=='#') continue;
 
            if(i-1>=0 && j-1>=0 && dp[i-1][j-1]!=-1){
                dp[i][j] = max(dp[i][j], dp[i-1][j-1]);
            }
            if(j-1>=0 && dp[i][j-1]!=-1){
                dp[i][j] = max(dp[i][j], dp[i][j-1]);
            }
            if(i+1<n && j-1>=0 && dp[i+1][j-1]!=-1){
                dp[i][j] = max(dp[i][j], dp[i+1][j-1]);
            }
 
            if(map[i][j]=='C' && dp[i][j]!=-1){
                dp[i][j]++;
            }
            if(map[i][j]=='O' && dp[i][j]!=-1){
                check = true;
                ans = max(ans, dp[i][j]);
            }
        }
    }
}
 
int main()
{
    memset(dp, -1, sizeof(dp));
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>s;
        for(int j=0; j<s.size(); j++){
            map[i][j] = s[j];
            if(map[i][j]=='R'){
                startX = i;
                startY = j;
                dp[i][j] = 0; // 경로의 시작!
            }
        }
    }
 
    rabbitMove();
 
    if(check){
        cout<<ans<<"\n";
    }else{
        cout<<"-1"<<"\n";
    }
    
    return 0;
}