[백준/BOJ] 백준 2169번 : 로봇 조종하기

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

2169번: 로봇 조종하기

다이나믹 프로그래밍을 통해 문제를 해결했는데, 이때 위치뿐만 아니라 해당 위치에서 어떤 방향으로 가는지까지 저장하여 문제를 해결했다. 로봇은 위쪽으로 움직일 수 없다는 것과, 한번 탐사한 지역은 탐사하지 않는 것을 이용하여 왼쪽 이동일때 (다음 이동은 왼쪽 또는 아래쪽 이어야 된다), 오른쪽 이동일때 (다음 이동은 오른쪽 또는 아래쪽 이어야 된다), 아래쪽 이동일때 (다음 이동은 왼쪽, 오른쪽, 아래쪽 모두 가능하다)를 고려하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n, m;
int board[1000][1000];
int cache[1000][1000][3];
int dxdy[3][2] = { {0,-1},{0,1},{1,0} };
int result;

void Pre()
{
	for (int i = 0; i < 1000; i++)
		for (int j = 0; j < 1000; j++)
			for (int k = 0; k < 3; k++)
				cache[i][j][k] = 100000001;
}

//here에서 here_dir 방향으로 갈때
int Solve(pair<int, int> here, int here_dir)
{
	if (here.first == n - 1 && here.second == m - 1)
		return board[n - 1][m - 1];

	int& ret = cache[here.first][here.second][here_dir];

	if (ret != 100000001)
		return ret;

	pair<int, int> there = make_pair(here.first + dxdy[here_dir][0], here.second + dxdy[here_dir][1]);

	if (there.first < 0 || there.first >= n || there.second < 0 || there.second >= m)
	{
		ret = -100000001;

		return ret;
	}

	ret = board[here.first][here.second];

	//왼쪽 이동일때 (다음 이동은 왼쪽 또는 아래쪽 이어야 된다)
	if (here_dir == 0)
	{
		ret += max(Solve(there, 0), Solve(there, 2));
	}

	//오른쪽 이동일때 (다음 이동은 오른쪽 또는 아래쪽 이어야 된다)
	else if (here_dir == 1)
	{
		ret += max(Solve(there, 1), Solve(there, 2));
	}

	//아래쪽 이동일때 (다음 이동은 왼쪽, 오른쪽, 아래쪽 모두 가능하다)
	else if (here_dir == 2)
	{
		int max_value;
		max_value = max(Solve(there, 0), Solve(there, 1));
		max_value = max(max_value, Solve(there, 2));

		ret += max_value;
	}

	return ret;
}

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

	Pre();

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	//출발점에서 오른쪽으로 가능 경우와, 아래쪽으로 가능 경우 비교
	result = max(Solve(make_pair(0, 0), 1), Solve(make_pair(0, 0), 2));

	cout << result << "\n";

	return 0;
}