[개쉬운 풀이] 백준 2169 로봇 조종하기 CPP (14일차)

문제

 

생각

1. 처음에는 단순하게 BFS로 풀면 된다고 생각했다. 그러나 각 배열에서 들어온 방향에 따라 결과가 달라질 수 있다는 것을 포착했다.

2. 따라서 2중 배열이 아닌 3중 배열을 통해 방향성을 고려하였다.

3. queue를 이용하다 보니 시간초과가 발생하였다. 따라서 이를 dfs와 dp를 활용한 수식으로 바꾸어 주었다.

 

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 1001;
const int INF = -1e9;

int N, M;
int map[MAX][MAX];
int dx[3] = {0,0,1}; //좌 우 밑
int dy[3] = {-1,1,0};
bool isVisited[MAX][MAX];
int dp[MAX][MAX][3];

void input(){
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
        }
    }
}

void init(){
    for(int i = 1; i < MAX; i++){
        for(int j = 1; j < MAX; j++){
            for(int k = 0; k < 3; k++){
                dp[i][j][k] = INF;
            }
        }
    }
}

int sol(int x, int y, int dir){
    if(x == N && y == M) return map[N][M];
    if(dp[x][y][dir] != INF) return dp[x][y][dir];

    isVisited[x][y] = true;
    
    int tmp = INF;
    for(int i = 0; i < 3; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 1 || ny < 1 || nx > N || ny > M || isVisited[nx][ny]) continue;
        tmp = max(tmp, sol(nx, ny, i));
    }
    
    isVisited[x][y] = false;
    dp[x][y][dir] = map[x][y] + tmp;
    return dp[x][y][dir];
}

int main(){
    input();
    init();
    cout << sol(1,1,0);

    return 0;
}