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

문제

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

2169번: 로봇 조종하기

NASA의 화성탐사로봇은 N*M배열의 화성을 탐사할려한다.

N*M배열의 각 칸에는 절댓값이 100을 넘지않는 정수들이 쓰여있고, 이 값은 그 칸을 방문했을때 얻을수있는 가치와 같다.

 

화성탐사로봇이 (1,1)위치에서 (N,M)위치까지 탐사할때, 얻을수있는 최대 가치를 구하는 문제였다.

 

풀이

얼핏?보면 그래프 문제같지만, 음수가중치가 존재하므로, dp로 풀어야했던 문제였다.

 

문제를 보면, 화성탐사로봇이 이동할수있는 경로는, (아래, 왼쪽, 오른쪽)이다.

즉, 아래에서 위로 올라가는 경우가 없으므로, y위치에 존재하는 칸들은 항상 y-1위치에 있는 칸에 어떠한 수를 더한 값이 된다.

따라서, y를 기준으로 탐색하는식으로 풀면 될것이라 생각하고 문제를 풀었다.

 

dp[y][x] = (y,x)위치에 오기까지 얻은 가치의 최댓값 이라고 가정하자.

 

(y,x)위치로 올수있는 경우의수는,

(순서대로 위에서 아래로 오는경로 왼쪽에서 오른쪽으로 오는경로 오른쪽에서 왼쪽으로 가는경로)

1. dp[y-1][x] (한칸 위에서 바로 아래로 내려오는경로 (y-1,x) -> (y,x) )

2. dp[y][x-1] ( (y-1,x-1) -> (y,x-1) -> (y,x) 로 오는경로 )

3. dp[y][x+1] ( (y-1,x+1) -> (y,x+1) -> (y,x) 로 오는경로 )

이렇게 3가지가 있다.

 

따라서 기초 점화식은

dp[y][x] = max(dp[y-1][x], max(dp[y][x-1],dp[y][x+1])) + arr[y][x];

가 된다.

 

하지만, 이렇게만 할경우, 왼쪽에서부터 순차적으로 계산하기때문에, 

(y-1,x+4) -> (y,x+4) -> (y,x+3) -> (y, x+2) -> (y, x+1) -> (y,x) 

와 같은 경로 (오른쪽 끝에서 오는경우) 를 봐주지 못한다. 

 

따라서, dp배열에 방향을 추가해, 왼쪽에서 오른쪽으로 가는경로, 오른쪽에서 왼쪽으로 가는경로를 각각 구해야한다.

이제 dp배열을 dp[y][x][방향(-> : 0, <- :1)] = (y,x)위치까지 (->, <-) 방향으로 왔을때 얻은 최대 가치라 하자.

 

이렇게 저장할경우, (y,x)위치까지 도달하는 최댓값은 max(dp[y][x][0], dp[y][x][1])로 구할수있다. (y,x 위치에 도달하기위해서 올수있는 경로는 항상 ->, <- 방향 둘중하나일것이므로)

 

또한, y-1위치의 방향은 y위치에 어떤 영향도 미치지 않는다.

즉, dp[y][x]['방향']은 (y-1,x)위치에 있는 최댓값(방향상관없이)을 취하는게 이득이다.

 

따라서 최종점화식은

dp[y][x][방향] = max(dp[y][x][방향],max(dp[y-1][x][0],dp[y-1][x][1])) + arr[y][x];

가 된다.

 

왼쪽 오른쪽 방향을 각각 따로 반복해서 구해야하며, 오른쪽 방향은 끝에서 부터 시작해야함을 주의하자.

 

음수 처리때문에 한번 틀렸었는데,

 

 

5 5

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

-1 -1 -1 -1 -1

출력 : 9

 

가 되어야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1269%20%EB%A1%9C%EB%B4%87%20%EC%A1%B0%EC%A2%85%ED%95%98%EA%B8%B0/main.cpp

devxb/JJUNalgo