[백준 2169] 로봇 조종하기 C++

www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

 

 

이 문제는 1,1에서 시작한 로봇이 N, M까지 도달하는 경로 누적 합 중 최대값을 구하는 문제 입니다.

 

DFS로, 각 공간마다 방향 왼쪽, 아래, 오른쪽으로 나누어서 풀면 되지만,

문제 조건 중에 N, M 제한이 1,000이기 때문에, 매번 갔던 길을 또 계산한다면 시간 복잡도가 어마하게 나올 것으로 생각되었습니다.

 

다이나믹프로그래밍을 사용해서, 각 지점에서 출발해서 N,M에 도달할 때의 최댓값을 저장해주면 된다고 생각했습니다.

 

예를 들어서, 4,5 지점에서 N,M인 10, 10에 가야되는데, 4,5 지점을 수차례 불러온다면 비효율적일 것입니다.

 

따라서, 4,5에서 출발해서 10,10까지 도달하는데 최대 값을 구해놓으면, 

다른 곳에서 출발하다가 4,5를 만나더라도, 그 최대값이 저장되어있기 때문에 최댓값만 반환하면 되는 것입니다.

 

 

하지만, 이 문제는 주의해야할 점은 두 가지가 있었습니다.

첫째, 문제조건에서 한번 탐사한 지역은 탐사하지 않는다.

둘째, 이동가능한 방향은 왼쪽,오른쪽,아래밖에 없다.

 

이 두가지를 만족하면서 문제를 풀려면, 해당 칸을 들어왔을 때를 따로 따로 계산을 해야한다는 것입니다.

추가적으로 visit나 check 배열을 만들어 경로가 시작된 지점부터는 check = true 표시를 하고, dfs 재귀함수에서 해당 지점이 벗어났을 때는 check = false표시를 해야지만 모든 경로 중에서 최대 경로를 구할 수가 있습니다.

 

해당 칸에 들어왔을 때, 따로 계산해야한다는 의미는, 3,5의 지점을 위에서 아래방향으로 들어왔을 때랑, 왼쪽으로 오른쪽으로 3,5를 들어왔을 때랑, 왼쪽에서 오른쪽으로 3,5를 들어왔을 때랑 다르게 계산해야한다는 점입니다. 

경로 방향이 다르기 때문에 방향별로 dp의 값들을 분리해서 저장해야합니다.

dp[x][y][dir]

 

dfs로 탐색하면서, 해당 지점에 들어왔을 때 check = true표시를 하여, 다시 돌아오는 경우가 없게 표시하고,

dfs로 반환하여 해당 지점을 벗어났을 땐 check=false로 해서, 다른 경로에서 check=false가 된 지점을 다시 방문할 수 있도록 만들어줍니다.

 

dp[x][y][dir]에 값이 존재하는 경우는 dp[x][y][dir] 값을 반환하면됩니다. 이미 계산한 값이기 때문에 더 이상 계산할 필요가 없습니다.

 

이 문제에서 주의할 점은, 음수가 배열에 포함되기 때문에 최댓값을 구하려면, 초기값을 -INF값을 주어야 한다는 점입니다.

배열 초기화를 0으로 하게 되면, 0은 최솟값이 아닌 어느정도 중간 값을 유지하기 때문에 max 비교 연산에서 최댓값을 구할 수 없습니다.

dp배열을 -INF값으로 초기화한 후, 사용하셔도 됩니다.

저 같은 경우는 dp배열을 -1로 초기화했는데, 다행이도 문제 테스트 케이스 중에서 모든 지점에서 -1이 나오는 경우가 없나 봅니다. (있더라도 -1만 추가적으로 계산해서 의미가 없나봅니다)

 

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;

const int MAX = 1001;
const int MINF = -987654321; // minus 최솟값 설정

int map[MAX][MAX];
long long dp[MAX][MAX][3]; // 0, 1, 2 (0은 아래, 1은 오른쪽, 2는 왼쪽)
bool check[MAX][MAX];


int dx[] = {1, 0, 0}; // 아래, 오른쪽, 왼쪽
int dy[] = {0, 1, -1};

int maxV;

long long dfs(int x, int y, int dir){
    if (x == n && y == m){
        
        return map[x][y]; // 지점에 도착하면 n,m에 있는 값 반환
    }

    long long &ret = dp[x][y][dir];
    if (ret != -1) return ret; // 이미 계산한 값이 있다면 반환
    ret = MINF; 				// 최댓값을 구하기 위해 최솟값을 삽입
    check[x][y] = true;

 

    for (int k = 0; k < 3; k++){
        int nx = x + dx[k];
        int ny = y + dy[k];

        if (nx < 1 || nx > n || ny < 1 || ny > m || check[nx][ny]) continue;

    

        ret = max(ret, dfs(nx, ny, k) + map[x][y]);
    }
    check[x][y] = false;


    return ret;
    
    
    
}

void solution(){

    
    cin >> n >> m;

    memset(dp, -1, sizeof(dp));

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            cin >> map[i][j];
        }

    long long result = dfs(1, 1, 0);

    cout << result << '\n';
}
int main(){


    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}