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

문제

NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.

지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.

각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

출력

첫째 줄에 최대 가치의 합을 출력한다.

풀이

기존에 흔하게 접할 수 있는 동적계획법 문제에서 오른쪽에서 왼쪽방향으로 이동할 수 있다는 조건하나만 추가 되었을 뿐인데 문제가 굉장히 까다로워졌다.

각 블록에서 이동할 수 있는 방향은 아래, 오른쪽, 왼쪽이므로 이 문제를 해결하기 위해서는 각 방향별로 얻을 수 있는 최댓값을 기록해야한다.
solve(int x, int y, int dir)은 (x,y)지점인 블록에서 dir방향으로 이동하였을때 얻을 수 있는 최댓값을 리턴한다. 한번 지나온 경로는 다시 갈 수 없으므로 check배열에 지나온 지점을 기록하며 탐색을 수행한다. 다음 이동할 경로가 범위 밖을 벗어나거나 이미 지나온 경로면 탐색을 수행하지않는다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int h,w;
int board[1000][1000];
int dp[1000][1000][3];
int check[1000][1000];
int dx[3] = {1,0,0};
int dy[3] = {0,1,-1};

int solve(int x, int y, int dir){
  if (x == h-1 && y == w-1) return board[x][y];

  int &ret = dp[x][y][dir];
  if (ret != -1) return ret;
  ret = -100000000;

  check[x][y] = 1;

  for (int i=0; i<3; i++){
    int nx = x+dx[i];
    int ny = y+dy[i];
    if (nx > h-1 || ny > w-1 || nx < 0 || ny < 0 || check[nx][ny]) continue;

    ret = max(ret, solve(nx,ny,i)+board[x][y]);
  }

  check[x][y] = 0;

  return ret;
}

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

  // ifstream cin;
  // cin.open("input.txt");

  cin >> h >> w;

  for (int i=0; i<h; i++)
    for (int j=0; j<w; j++)
      cin >> board[i][j];
  
  memset(dp, -1, sizeof(dp));

  cout << solve(0,0,0);

}