[BOJ 1937] 욕심쟁이판다

/*
	토마토랑 비슷한 문제인거 같아서 비슷하게 접근했다가 시간초과를 했다.
	그래서 코드를 참고하여 공부했다.
	https://github.com/JaVashit/StudyForSamsung/blob/master/Solving_Problem/Park.K.S/
	*/
	#include<cstdio>
	#include<vector>
	#include<algorithm>
	using namespace std;
	int arr[510][510]; // 대나무 숲의 정보
	int check[510][510]; // 좌표에서 방문할 수 있는 최대 깊이
	int dx[] = { 0,0,-1,1 };
	int dy[] = { 1,-1,0,0 };
	int n,ans=0;
	vector<int> v;
	int dfs(int x, int y)
	{
	if (check[x][y]) return check[x][y];
	// 검사하여 check[x][y]에 정보가 존재하는 경우 해당하는 정보를 반환
	bool flag = false;
	// 주변의 방문 가능 지점 유무를 검사하기 위한 flag
	for (int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
	if (arr[nx][ny] > arr[x][y]) {
	flag = true;
	check[x][y] = max(check[x][y], dfs(nx, ny) + 1);
	}
	}
	}
	if (flag == false) return check[x][y] = 1;
	else return check[x][y];
	}
	void Init(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	scanf("%d", &arr[i][j]);
	}
	}
	}
	int main()
	{
	Init();
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	if (!check[i][j]) {
	ans = max(ans, dfs(i, j));
	}
	}
	}
	return 0;
	}