[BOJ - 2169] 로봇 조종하기

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

DFS와 DP를 합쳐서 풀어야 시간 초과가 안 나는 문제이다.

구현 자체는 DFS와 동일하게 구현하면 되는데 int& ret = dp[x][y][dir]을 통해서 탑 다운 방식으로 DP를 구현해준다.

재귀를 통해서 dp값을 갱신하는데 이러면 시간 복잡도가 훨씬 줄어든다.

기존에는 전부를 확인해서 가져오던 것들을 최대의 값(DP)에서 시작하기 때문이다.

 

코드

#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
int n, m;
int map[1010][1010];
bool visited[1010][1010];
// 왼쪽, 오른쪽, 아래
int dx[3] = { 0,0,1 };
int dy[3] = { -1,1,0 };
int dp[1010][1010][3];

bool is_possible(int x, int y) {
	return !(x<0 || y<0 || x>n - 1 || y>m - 1 || visited[x][y]);
}

int dfs(int x, int y, int dir) {
	if (x == n - 1 && y == m - 1) {
		return map[x][y];
	}

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

	ret = -1e9;
	visited[x][y] = true;

	for (int i = 0; i < 3; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];
		if (is_possible(next_x, next_y)) {
			ret = max(ret, map[x][y] + dfs(next_x, next_y, i));
		}
	}

	visited[x][y] = false;
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

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

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

	int answer = dfs(0, 0, 0);
	cout << answer << endl;

	return 0;
}