[백준] 1937번 욕심쟁이 판다 (DFS + DP)

-문제

 

-코드

#include<stdio.h>
#include<algorithm>
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int map[500][500], dp[500][500];
int n, res;

int DFS(int x, int y)
{
	if (dp[x][y] > 0) return dp[x][y];
	else
	{
		dp[x][y] = 1;
		for (int i = 0; i < 4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 0 || yy < 0 || xx >= n || yy >= n) continue;
			if (map[x][y] < map[xx][yy])
			{
				dp[x][y] = max(dp[x][y], DFS(xx, yy) + 1);
			}		
		}
	}
	return dp[x][y];
}

int main()
{
	scanf("%d", &n);

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

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			res = max(res, DFS(i, j));
		}
	}
	printf("%d", res);
	return 0;
}