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

https://www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001][1001];
int dp[1001][1001][3];
int side[3][2] = { {0,-1},{0,1},{1,0} };
bool visit[1001][1001];
int N, M;
int DFS(int y, int x, int dir)
{
	if (y == N - 1 && x == M - 1)
		return arr[y][x];

	if (dp[y][x][dir] != -987654321)
		return dp[y][x][dir];

	for (int i = 0; i < 3; i++)
	{
		int ny = y + side[i][0];
		int nx = x + side[i][1];

		if (ny >= 0 && nx >= 0 && nx < M && ny < N && visit[ny][nx] == false)
		{
			visit[ny][nx] = true;
			dp[y][x][dir] = max(dp[y][x][dir], arr[y][x] + DFS(ny, nx, i));
			visit[ny][nx] = false;
		}
	}

	return dp[y][x][dir];
}
int main(void)
{
	cin >> N >> M;
	for(int i=0;i<N;i++)
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];

			dp[i][j][0] = -987654321;
			dp[i][j][1] = -987654321;
			dp[i][j][2] = -987654321;
			visit[i][j] = false;
		}
	visit[0][0] = true;
	cout << DFS(0, 0, 0);

}

dp[y][x][dir] : y,x 좌표에 dir 방향으로 입장했을 때의 최댓값

 

(0,0)에서 시작하여 (N-1,M-1) 좌표에 도착할 때까지 다음 좌표로 DFS를 합니다

다음 좌표에 입장할때의 방향은 3가지로 DFS(ny,nx,i)로 i를 3가지 방향으로 호출하게 합니다.

(N-1, M-1)에 도착 시 이제 (N-1, M-1)부터의 값을 더하며 진입한 길을 후진하며 (0,0)에 최댓값이 완성되게 만들 겁니다.

dp[y][x]에 각각 3가지 방향으로 입장했을 때의 최댓값이 다르므로 dp[y][x][dir]로 구분하여준 겁니다.

dp[y][x][dir] = max(dp[y][x][dir], arr[y][x] + DFS(ny, nx, i)); 

 

이미 y,x 좌표에 dir 방법으로 도착한 경우의 최댓값이 있을 경우 그 값을 그냥 반환해주면 됩니다.

또 dir방법으로 그 좌표에서 탐색을 시작하는 것은 시간 낭비이기 때문입니다.

아래의 코드처럼 반환해줍니다.

	if (dp[y][x][dir] != -987654321)
		return dp[y][x][dir];