백준 2169번 로봇 조종하기 문제 해설, 동적 계획법 변형 문제 완벽하게 이해하기
by injae Kim
백준 2169번 로봇 조종하기 문제 해설
solved.ac 기준 골드 1 난이도의 문제입니다. 동적계획법, 그래프 를 사용하여 문제를 해결하였습니다.
동적 계획법의 가장 기본적인 문제인 최대 합 경로 문제와 매우 유사하지만, 문제가 살짝 변형되어 기본적인 접근방법으로는 해결하기 쉽지 않은 문제였습니다.
이 문제를 풀기 전에 최대 합 경로 문제를 살펴보고 오시는 것 을 추천합니다. 이 문제에서 대부분의 아이디어를 얻어서 해결하였습니다.
문제
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만,
로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만,
위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜
오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서,
탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다.
배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.
출력
첫째 줄에 최대 가치의 합을 출력한다.
예제입력
5 5
10 25 7 8 13
68 24 -78 63 32
12 -69 100 -29 -25
-16 -22 -57 -33 99
7 -76 -11 77 15
예제출력
319
문제 풀이
이 문제는 동적 계획법의 가장 기본적인 문제인 최대 합 경로 문제 와 매우 유사합니다.
다른점은 최대 합 경로 문제 에서는 (오른쪽, 아래) 만 갈 수 있다면, 이 문제에서는 (왼쪽, 오른쪽, 아래) 로 왼쪽 으로 가는 경우 가 추가되었다는 점 이죠. 그 밖의 큰 차이점은 없습니다.
하지만, 왼쪽으로 가는 경우가 추가되면서 메모이제이션 적용 방법 자체가 바뀌어 버립니다. 부분문제의 정의가 달라지기 때문이죠. 왜 그런지 천천히 살펴보겠습니다.
우선 생각하기 쉬운 경우인 로봇이 (오른쪽, 아래) 로 만 갈수 있는 경우먼저 동적 계획법 적용 방법을 알아보죠!
로봇이 (오른쪽, 아래) 로 갈 수 있는 경우 입니다.
로봇이 (오른쪽, 아래) 로 만 갈수 있으므로, 맨 왼쪽 위에서 로봇이 출발 할 때 갈 수 있는 곳은 그림과 같습니다.
한번 더 로봇을 이동시켜 보겠습니다. 규칙이 보이시나요?
로봇이 (오른쪽, 아래) 로만 가는 경우 로봇이 어디서 왔는지는 중요하지 않습니다! 왜냐하면 로봇이 왔던 경로로 되돌아 갈 수 없기 때문이죠.
따라서, 전체 문제를 이전 문제와 상관없는 부분 문제로 분해할 수 있으므로, 메모이제이션을 적용할 수 있습니다. 이때 부분 문제의 정의는 다음과 같습니다.
maxPath (x, y) = 현재 좌표 x, y 에서 가장 탐사 가치가 높게 갈 수 있는 경로의 최대 가치 합
부분 문제의 정의를 위와 같이 한다면, 현재의 maxPath() 값 은 오른쪽으로 이동했을 때 의 maxPath() 값 과 아래로 이동했을 때 의 maxPath() 값 중 최대값이 됩니다.
이런식으로 동적계획법이 적용되는 이유는, 로봇은 오른쪽과 아래로 밖에 움직이지 못하기 때문에 이전의 왔던 경로로 돌아갈 수 없기 때문입니다.
하지만, 왼쪽으로 가는 경우 가 추가된다면 이런 동적계획법을 동일하게 적용할 수 있을까요?
그림으로 살펴보겠습니다.
로봇이 (왼쪽, 오른쪽, 아래) 로 이동할 수 있는 경우 를 살펴보겠습니다.
로봇이 왼쪽으로 이동할 수 있므로, 이에 따라서 로봇이 이 전에 왔던 경로로 돌아갈 수 가 있네요!
즉, 우리가 앞서 정의했던 부분 문제가 이전의 상태에 의존하므로, 같은 원리로 메모이제이션 할 수 없습니다.
이를 해결하기 위해 부분 문제의 정의를 살짝 바꿔보겠습니다.
로봇이 왼쪽, 오른쪽, 아래 로 이동하는 방향에 따라서 부분 문제를 분리해야 하므로, 부분 문제의 정의에 로봇이 이동한 방향인 direction 을 추가 해 주었습니다.
로봇이 이동한 방향을 추가 하게 되면, 왼쪽, 오른쪽, 아래 에 따라서 각각 다르게 메모이제이션을 적용하게 되므로 방향 정보가 없이 메모이제이션 을 할 때에 발생하는 이전 경로로 되돌아 올 수 있다 는 문제점을 해결 할 수 있습니다.
여기까지의 아이디어로 구현하면 출력이 정답보다 더 크게 나옵니다. 왜그럴까요? 바로 문제의 조건에서 한번 탐사한 칸 은 다시 탐사 하지 않는다 라는 조건이 있기 때문입니다.
따라서, 여러 칸을 중복하여 탐사 할 수 있기 때문에 출력이 정답보다 크게 나올 수 있습니다.
이를 해결하기 위해 현재 경로에서 탐색했던 칸 은 다시 돌아가지 않는다 라는 조건을 추가해서 구현해야 합니다.
만약 로봇이 (오른쪽, 아래) 로만 움직인다면 왔던 경로를 다시 돌아갈 일 도 없을겁니다. 하지만, 왼쪽으로 이동하는 경우에는 왔던 경로로 돌아갈 수 있습니다.
위의 그림에서 처럼 왼쪽으로 이동 후 오른쪽 으로 이동하는 경우 이미 탐색한 칸 을 다시 탐색하게 되죠.
이를 방지하기 위해, 재귀적으로 칸을 탐색할 때 마다 visited [x] [y] 배열을 사용하여 현재 경로에서 탐색 한 칸에 true 를 넣어주는 식으로 해결 할 수 있겠네요.
여기까지의 아이디어를 그대로 코드로 구현해보겠습니다!
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
int row, col;
int map[1009][1009];
int cache[3][1009][1009];
bool visited[1009][1009];
int dx[3] = { 0, 0, 1 };
int dy[3] = { -1, 1, 0 };
int getMax(int x, int y, int direction)
{
// 방향정보를 추가하여 메모이제이션
int& ret = cache[direction][x][y];
if (x == row - 1 && y == col - 1)
return map[x][y];
if (ret != 98765432)
return ret;
ret = -98765432;
// 왼쪽, 오른쪽, 아래 방향으로 이동 시의 최대 경로값을 반환
for (int k = 0; k < 3; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= row || ny < 0 || ny >= col)
continue;
if (visited[nx][ny])
continue;
// 탐사했던 칸 을 다시 탐사하지 않기 위해
visited[nx][ny] = true;
ret = max(ret, map[x][y] + getMax(nx, ny, k));
visited[nx][ny] = false;
}
return ret;
}
void solve()
{
for (int k = 0; k < 3; k++)
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
cache[k][i][j] = 98765432;
visited[0][0] = true;
int max = -98765432;
for (int i = 0; i < 3; i++)
// 왼쪽 맨 위의 칸 에서 왼쪽, 오른쪽, 아래로 이동시의 최대 경로 합 을 반환
if (max < getMax(0, 0, i))
max = getMax(0, 0, i);
cout << max << endl;
}
int main()
{
cin >> row >> col;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
int temp; cin >> temp;
map[i][j] = temp;
}
}
solve();
return 0;
}
문제의 접근방식과 아이디어를 그대로 소스코드로 구현하였습니다.
문제풀이 후기
동적 계획법 기본 문제와 매우 유사한 점 이 많았지만, 이동 할 수 있는 방향이 단 하나만 추가 되어도 부분 문제의 정의가 바뀌므로 전체 알고리즘을 다시 설계해야 하며 그 때 발생할 수 있는 문제점들 또한 다시 생각해 봐야 한 다는 것 을 알려줬던 문제 였습니다.
왼쪽으로 이동할 수 있다는 점 이 불러오는 문제점들에 집중하여 단계적으로 접근하면 충분히 해결할 수 있었을 것 이라고 생각합니다.