[C++][백준] 욕심쟁이 판다 (1937) - dp

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

 

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

 

풀이

판다가 이동할 수 있는 칸의 수의 최댓값을 구하는 문제입니다. 

 

문제의 조건을 정리해보면 아래와 같습니다.

1. 판다는 현재 위치에서 대나무를 다 먹는다.

2. 상, 하, 좌, 우로 이동한다. 단, 현재 위치보다 대나무가 많은쪽으로 이동할 수 있다.

3. 최대한 많은 칸을 이동해야 한다.

 

먼저 2차원 배열 Map에 대나무 숲에 대한 정보를 입력받습니다. 

저는 DP로 문제를 풀기 위해 2차원 배열 Memo를 생성하였습니다.

Memo의 초기값은 0이며, 해당 칸을 밟았을 때 이동할 수 있는 칸의 수의 최댓값을 담고있습니다.

 

"현재 위치보다 대나무가 많은쪽으로 이동할 수 있다" 조건에 초점을 맞춰보겠습니다.

이 말은 즉 "대나무가 가장 많은쪽에서는 다른 위치로 이동할 수 없다"라고 생각할 수 있습니다.

즉 Memo(해당 칸을 밟았을 때 이동할 수 있는 칸의 수의 최댓값)를 1(현 위치는 밟았기 때문)로 채울 수 있습니다.

 

이렇게 대나무 수가 많은 위치부터 적은 위치로 Bottom-up(바텀업)느낌으로 Memo 배열을 채워주면 

어떤 칸을 밟았을 때 이동할 수 있는 칸의 수가 최대인지 구할 수 있습니다.

 

그림으로 살펴보면 이해가 쉬울 것 같습니다.

대나무가 가장 많은 위치(16)에서는 그 어느곳으로도 이동할 수 없기 때문에 

해당 칸을 밟았을 때 이동할 수 있는 칸의 수의 최댓값은 자기 자신을 밟은 1칸입니다.

이 값을 Memo 배열에 기록해둡니다.

 

 

그 다음 대나무가 15개 있는 위치에서도 그 어느곳으로도 이동할 수 없기 때문에 

해당 칸을 밟았을 때 이동할 수 있는 칸의 수의 최댓값은 자기 자신을 밟은 1칸입니다.

이 값을 Memo 배열에 기록해둡니다.

 

 

마찬가지로 14, 13, 12 칸 모두 자기 자신을 제외한 칸으로 이동할 수 없기 때문에 Memo 배열을 1로 채워주었습니다.

이 때 대나무가 11개 있는 위치에서는 대나무가 15개인 위치로 이동할 수 있습니다. 

따라서 대나무 15 위치의 Memo를 참고하여 (15개인 위치를 밟았을 때 이동할 수 있는 칸의 최댓값 + 1)을 Memo에 기록합니다.

 

 

이번엔 대나무가 4개 있는 위치를 살펴보도록 하겠습니다.

해당 위치에서는 모든 위치로 이동할 수 있습니다. 

 

이 때 ↑, ←, ↓ 중 어느 방향으로 이동해야 가장 많은 칸을 이동할 수 있을까요?

우리는 Memo 값만 비교해보고 결정할 수 있습니다. ↑(2), ←(3), ↓(1) 

Memo값이 가장 큰 왼쪽 ←(3) 정보를 통해 4 입장에서는 직접 가보지 않아도 5 위치만 밟으면 최대 3칸을 이동할 수 있다는 것을 파악할 수 있습니다. 

 

 

 

이렇게 모든 Memo 배열을 채울 수 있고

이동할 수 있는 칸의 최대 수는 Memo 배열의 최댓값 4가 됩니다.

 

전체 코드는 아래와 같습니다.

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

int N;
const int MAX = 520;
int map[MAX][MAX];
int memo[MAX][MAX] = { 0, };

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};

struct myData {
	int count;
	int x;
	int y;
};
vector<myData> list;

bool comp(const myData& a, const myData& b) {
	if (a.count == b.count) {
		if (a.x == b.x) {
			return a.y > b.y;
		}
		else {
			return a.x > b.x;
		}
	}
	else {
		return a.count > b.count;
	}
}

int main() {
	cin >> N;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
			list.push_back({ map[i][j], i, j});
		}
	}
	sort(list.begin(), list.end(), comp);

	int answer = 0;
	for (int i = 0; i < list.size(); i++) {
		int curTree = list[i].count;
		int curX = list[i].x;
		int curY = list[i].y;

		int maxTree = 0;
		for (int j = 0; j < 4; j++) {
			int nextX = curX + dirX[j];
			int nextY = curY + dirY[j];

			if (map[nextX][nextY] <= map[curX][curY]) continue;
			if (memo[nextX][nextY] > maxTree) {
				maxTree = memo[nextX][nextY];
			}
		}
		memo[curX][curY] = maxTree + 1;
		if (memo[curX][curY] > answer) {
			answer = memo[curX][curY];
		}
	}
	cout << answer;

	return 0;
}

 

Memo 배열의 정의는 해당 칸을 밟았을 때 이동할 수 있는 칸의 수의 최댓값이기 때문에

밟을 수 없는 경우, 즉 현재 칸보다 값이 같거나 큰 경우에는 Memo값을 참조할 수 없습니다.

따라서 continue로 처리하였습니다.