백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/2169

아이디어

• DP - DFS 방법으로, 끝에서부터 시작하여 거꾸로 시작점까지 오면 될것으로 예상

• 그런데 왼쪽으로 이동할 수 있다는 것이 기존 문제 유형과 다른점

• 왼쪽에서 이동할경우 무한루프가 발생할 수 있으니까, 이전 좌표를 인식하고, 해당 좌표 제외한것만 DP 하면 어떨까?

  • 이러면 무한루프 발생할 수 있음

• DP에 각 방향을 정해서, 해당 방향에서 들어온 경우를 나눔

  • DP[y][x]에서 k 방향으로 들어온 경우, DP[y+dy[k]][x+dx[k]]방향에서는 k방향으로 들어온것 제외하고 계산
  • 마지막에 k값중 최대값을 답으로

• 점화식

  • DP[y][x][k] = y, x 좌표에서 이전에 k방향에서 들어와서 탐사한 결과의 최대값
  • 예시 : DP[y][x][0] = DP[y+dy[k0]][x+dx[0]][0] + DP[y+dy[k0]][x+dx[0]][1]

시간복잡도 계산

• 한 노드는 *3번
• O(NN3) = 3e6 >> 가능

인트 계산

• DP가 가질수 있는 최대값 : 1000 * 1000 * 100 = 1e8 >> INT 가능

코드

#include <iostream>
 
using namespace std;
 
int map[1010][1010];
int dp[1010][1010][3];
int chk[1010][1010];
 
const int inf = -1e9;
int dy[] = {-1,0,0};
int dx[] = {0,1,-1};
int N,M;
// pre 값이라면 제외
int get_dp(int y, int x, int pre) {
    // dp가 이미 결정된 값인지 확인하는 여부 >> 초기화를 -1e9로
    if(dp[y][x][pre] != inf) return dp[y][x][pre];
    int maxv = inf;
    for(int k=0; k<3; k++) {
        if(pre == 1) if(k==2) continue;
        if(pre == 2) if(k==1) continue;
        int py = y +dy[k];
        int px = x +dx[k];
        if(py>=0 && py<N && px>=0 && px < M) {
            maxv = max(maxv, get_dp(py, px,k) + map[y][x]);
        }
         
    }
 
    return dp[y][x][pre] = maxv;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&dp[0][0][0], &dp[1009][1009][3], inf);
    fill(&chk[0][0], &chk[1009][1010], false);
    
    cin >> N >> M;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    for(int k=0; k<3; k++) {
        dp[0][0][k] = map[0][0];
    }
    
    
    cout << max(max(get_dp(N-1,M-1,0), get_dp(N-1,M-1,1)), get_dp(N-1,M-1,2)) << '\n';
    
    
    return 0;
}
 

문제유형

• 케이스 2차원 DP : 조건이 복잡할 때, 각 케이스에서의 dp

  • https://www.acmicpc.net/problem/2579
  • https://www.acmicpc.net/problem/1309
  • https://www.acmicpc.net/problem/2169

• DP - DFS

  • DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
  • 특히 2차원에서 상하좌우를 모두 고려해줘야할 때
  • https://www.acmicpc.net/problem/1520
  • https://www.acmicpc.net/problem/1937