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

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

기본적인 아이디어는 DP입니다. 그런데 기존의 비슷한 문제와 같이 D[i][j]를 (1,1)에서 (i,j)까지 갈 때의 최대 가치 합으로 두면 D[i][j] = max(D[i-1][j], D[i][j-1], D[i][j+1]) + map[i][j]와 같은 형태가 될텐데 이렇게 될 경우 한 번 탐사한 지역은 탐사하지 않기로 한다는 조건을 고려하는 것이 불가능합니다. 그렇기 때문에 3차원 DP를 사용해

D[i][j][0] : (1,1)에서 (i, j)까지 갈 떄의 최대 가치 합. 단 (i, j)로 도달하기 직전 로봇은 (i, j)의 왼쪽에 위치함

D[i][j][1] : (1,1)에서 (i, j)까지 갈 떄의 최대 가치 합. 단 (i, j)로 도달하기 직전 로봇은 (i, j)의 오른쪽에 위치함

D[i][j][1] : (1,1)에서 (i, j)까지 갈 떄의 최대 가치 합. 단 (i, j)로 도달하기 직전 로봇은 (i, j)의 윗쪽에 위치함

으로 둘 경우

D[i][j][0] = max(D[i][j-1][0], D[i][j-1][2]) + arr[i][j]

D[i][j][1] = max(D[i][j+1][1], D[i][j+1][2]) + arr[i][j]

D[i][j][2] = max(D[i-1][j][0], D[i-1][j][1], D[i-1][j][2]) + arr[i][j] 라는 식을 얻을 수 있습니다.

D를 채우는 순서가 굉장히 중요합니다. 잘 생각해보면

D[1][1~M][2] => D[1][1~M][0] => D[1][M~1][1] => D[2][1~M][2] => D[2][1~M][0] => D[2][M~1][1] => D[3][1~M][2] => D[3][1~M][0] => D[3][M~1][1] => ... 으로 채워야함을 알 수 있습니다.

DP 테이블을 구하는 것도 다소 복잡한데 실제로 코딩을 할 때 경계에 있는 것들을 예외처리하는 것도 살짝 까다로웠습니다.

https://github.com/encrypted-def/BOJ/blob/master/2169.cpp