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

2학년때 풀다가 시간초과만 나와서 던졌던 문제인데 오랜만에 재도전 해보았음...ㅋㅋㅋ

 

문제 설명

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

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

 

문제 풀이

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

int f_size;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int panda_road(int** forest, int** dp, int x, int y)
{
	// 이미 dp가 정해진 곳은 더 계산 안해도 됨
	if (dp[x][y] != 1) return dp[x][y];

	int px, py;
	for (int i = 0; i < 4; i++) {
		px = x + dx[i];
		py = y + dy[i];
		if (px >= 0 && px < f_size && py >= 0 && py < f_size && forest[x][y] > forest[px][py]) {
			// 현재 숲 주위에 더 작은 숲이 있으면, 그 숲들의 dp값 중 최대인 것을 찾아 +1 
			dp[x][y] = max(dp[x][y], panda_road(forest, dp, px, py) + 1);
		}
	}
	return dp[x][y];	
}
int main() {

	cin >> f_size;
	int panda_max = 0;
	int ** forest = new int*[f_size]; // 대나무숲
	int ** dp = new int* [f_size]; // 최대로 방문할 수 있는 값

	for (int i = 0; i < f_size; i++)
	{
		forest[i] = new int[f_size];
		dp[i] = new int[f_size];
		for (int j = 0; j < f_size; j++)
		{
			cin >> forest[i][j];
			dp[i][j] = 1;
		}
	}

	for (int i = 0; i < f_size; i++) {
		for (int j = 0; j < f_size; j++) {
			cout << i << j << endl;
			panda_max = max(panda_max, panda_road(forest, dp, i, j));
		}
	}	
	cout << panda_max;
}

 

• dp 는 이미 계산된 것이면 그대로 쓰기만 하면 된다. 그래서 1(초기화값)이 아닌 곳은 계산하지 않고 바로 return
• 예전엔 나무 개수가 적은 순으로 정렬해서 DFS를 시작하면 더 빠를 줄 알고 정렬된 숲을  벡터를 만들고 맵을 만들고 ... 어쩌구 복잡하게 접근했었는데, 애초에 dp 개념이 이미 계산된 것은 그대로 사용하는 거라 정렬해서 시작할 필요가 없었다. 그래서 다 지우고 처음에 입력받은 forest 배열과 dp 배열만 남겨서 했더니 통과.
• 아 그리고 dx, dy 배열은 상하좌우로 접근할 일이 있을때 많이들 저런 식으로 하는 것 같았다. 깔끔한 방법인 것 같아서 나도 앞으로 이렇게 풀기로 했음
• Array는 전역변수로 배열 크기만 선언하면 0으로 초기화해준다는데, 다음에는 그렇게 해서 매개변수를 줄여야겠다