백준 1937: 욕심쟁이 판다

문제 요약

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

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

문제 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• DFS

문제 풀이

주어진 2차원 배열을 탐색하는 DP문제이다. 우선 경계조건은, 자신의 위치에서 상하좌우 어디로든 이동할 수 없을 때이고, 그때에는 1을 반환해야 한다. 자기자신의 위치를 포함하여 이동할 수 있는 거리가 1이기 때문. 결국 dp[i][j]에는 i,j위치에서 얼마나 멀리 이동할수 있는지의 최대값이 저장된다. 최소 거리는 0이므로 기본 0으로 초기화하여도 무방하다. 그리고 상화좌우 중 자신보다 큰값을 가지고 있는 위치로 탐색하는데, 이동한 위치의 이동 거리 중 최댓값으로 저장하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int n, res;
int ary[500][500], dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, dp[500][500];

int dfs(int i, int j) {
	if (dp[i][j] != 0) return dp[i][j];
	dp[i][j] = 1;
	int temp = 0;
	for (int k = 0; k < 4; k++) {
		int ni = i + dir[k][0];
		int nj = j + dir[k][1];
		if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
			if (ary[i][j] < ary[ni][nj])
				 temp = max(dfs(ni, nj), temp);
		}
	}
	dp[i][j] += temp;
	return dp[i][j];
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &ary[i][j]);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			res = max(dfs(i, j), res);
	cout << res;
}