[백준] 로봇 조종하기 (2169번)

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

5 5 10 25 7 8 13 68 24 -78 63 32 12 -69 100 -29 -25 -16 -22 -57 -33 99 7 -76 -11 77 15

예제 출력 1 복사

319

---

만만하게 봤다가 틀렸다.

처음엔 bfs로 했는데 생각해보니 bfs로 하면 방문할 때마다 해당 좌표의 dp 값이 바뀌므로 무한루프를 돌기 때문에 틀린다. 

그 다음엔 dfs로 했는데 역시나 틀렸고 시간초과가 떴다.

 

dp와 dfs를 섞어야 하는 문제였고 그렇게 풀어서 맞았다.

특히 dp에서 방향에 따른 값도 기록을 해야해서 3차원 배열로 만들어야 했다.

그 후 해당 지점에서 3가지 방향으로 각각 방문하면서 얻을 수 있는 최대 값을 얻어서 해당 좌표에 기록한다.

그렇게 모든 지점을 모든 방향으로 방문하고 나서야 정답을 구할 수 있었다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%A1%9C%EB%B4%87%20%EC%A1%B0%EC%A2%85%ED%95%98%EA%B8%B0%20(2169%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
#define INF 987654321
using namespace std;
int N, M, res;
int dp[1001][1001][3];
int p[1001][1001];
int visit[1001][1001];
int dx[4] = { 0,0,1 };
int dy[4] = { -1,1,0 };

int dfs(int x, int y, int dir) {
	if (x == N && y == M) {
		return p[x][y];
	}
	if (dp[x][y][dir] != -INF) return dp[x][y][dir];

	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 || visit[nx][ny] != 0) continue;
		visit[nx][ny] = 1;
		dp[x][y][dir] = max(dp[x][y][dir], dfs(nx, ny, i) + p[x][y]);
		visit[nx][ny] = 0;
	}
	return dp[x][y][dir];
}

int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++) {
			cin >> p[i][j];
			dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = -INF;
		}
	visit[1][1] = 1;
	cout<<dfs(1, 1, 0);
}