로봇 조종하기

문제 링크

발상

이전 DP 단원에 내리막 길이라는 비슷한 문제가 있지만 그 문제는 모든 경로가 반드시 일방통행임이 보장되었기 때문에 별도의 방문 체크가 필요하지 않았다. 그에 반해 이 문제는 양방향 통행이 가능하므로 별도의 방문 확인이 없다면 무한 루프에 빠지게 된다. BFS로 풀 경우, 그 방문 확인을 모든 탐색 루틴마다 별도로 해줘야 하기 때문에 최대 입력 크기인 $1000\times 1000$ 입력에서는 $10^6$개의 배열을 탐색 루틴마다 가지고 있어야 한다는 소리가 된다. 여기까지만 생각해도 BFS 풀이는 불가능하다.

Y축은 일방향이기 때문에 이전 최적값을 불러오는게 수월한데 X축은 양방 움직임이 가능해서 이전 값을 불러오는게 어려워 보인다. ↑ 이렇게 생각하도록 문제가 짜여있다. 로봇은 X축으로 양방향 이동이 불가능하다. 조건 중 ‘같은 지역을 두번 이상 탐사할 수 없다’는 조건이 존재하는 것을 기억하는가? 같은 Y축에서 양방향으로 움직이려면 반드시 이전에 방문한 지역을 거쳐야 한다. X축에서 ‘양방향 중 하나’로만 움직일 수 있다고 생각하는 것이 더 명확한 표현이다. 양의 방향과 음의 방향으로 움직인 2개의 최적값 리스트를 만들고 그 두 리스트에서 더 큰 값을 취하면 문제를 해결할 수 있다.

점화식

$$\{\begin{array}{l}{n}_{i,j}=\text{i,j위치에서 얻을 수 있는 최대 가치}\\ a_{i,j}=\text{i,j위치의 가치}\\ L_{i,j}=\text{i행에서 왼쪽으로만 움직였을 때 j열에서의 최대 가치}\\ R_{i,j}=\text{i행에서 오른쪽으로만 움직였을 때 j열에서의 최대 가치}\\ n=\text{맵 세로 길이}\\ m=\text{맵 가로 길이}\end{array}$$ $$\begin{array}{rl}{L}_{i,j}& =\underset{j=1\to m}{\max }(n_{i-1,j},L_{i,j-1})\\ R_{i,j}& =\underset{j=m\to 1}{\max }(n_{i-1,j},R_{i,j+1})\\ n_{i,j}& =\underset{j=1\to m}{\max }(L_{i,j},R_{i,j})\end{array}$$

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int n, m; cin >> n >> m; vector<vector<int>> arr(n + 1, vector<int>(m + 1)), dp(n + 1, vector<int>(m + 2, -21e8));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	dp[0][1] = 0; 
	for (int i = 1; i <= n; i++) {
		vector<int> s1(m + 2, -21e8), s2(m + 2, -21e8);
		for (int j = 1; j <= m; j++) {
			s1[j] = (dp[i - 1][j] > s1[j - 1] ? dp[i - 1][j] : s1[j - 1]) + arr[i][j];			
		}
		for (int j = m; j >= 1; j--) {
			s2[j] = (dp[i - 1][j] > s2[j + 1] ? dp[i - 1][j] : s2[j + 1]) + arr[i][j];			
		}
		for (int j = 1; j <= m; j++) {
			dp[i][j] = s1[j] > s2[j] ? s1[j] : s2[j];
		}
	}	
	cout << dp[n][m];
	return 0;
}