[PS][완전탐색][DFS]/[BOJ][1937][욕심쟁이 판다]

boj1937.cpp

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int n=0, input =0, ans=0;
int map[501][501];
int dp[501][501];
bool visited[501][501];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1, 0,0};

int max(int a, int b){
	return a < b ? b : a;
}

int dfs(int x, int y){
	if(dp[x][y]) return dp[x][y];
	int nx=0, ny=0;
	for(int k=0; k<4; k++){
		nx = x + dx[k];
		ny = y + dy[k];
		if(nx <0 || nx >=n) continue;
		if(ny <0 || ny >=n) continue;
		if(map[x][y] >= map[nx][ny]) continue;
    dp[x][y] = max(dp[x][y], dfs(nx,ny)+1);
	}
	return dp[x][y];
}

int main (void){
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	cin>> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>> map[i][j];
		}
	}
	memset(dp, 0, sizeof(dp));
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			ans = max(ans,dfs(i,j));
		}
	}
	cout << ans + 1<<"\n";
	return 0;
}

//시간초과 코드

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int n=0, input =0, ans=0;
int map[501][501];
int life[501][501];
bool visited[501][501];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1, 0,0};
void dfs(int x, int y, int depth){
  life[x][y] = depth;
	visited[x][y] = true;
	int nx=0, ny=0;
	for(int k=0; k<4; k++){
		int nx = x + dx[k];
		int ny = y + dy[k];
		if(nx <0 || nx >=n) continue;
		if(ny <0 || ny >=n) continue;
		if(visited[nx][ny]) continue;
		if(map[x][y] >= map[nx][ny]) continue;
    if(life[nx][ny] >= depth+1) continue;
		dfs(nx,ny, depth+1);
	}
	visited[nx][ny] = false;
	ans = ans < depth ? depth : ans;
}

int main (void){
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	cin>> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>> map[i][j];
		}
	}
	memset(life, 0, sizeof(life));
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			memset(visited, false, sizeof(visited));
			if(life[i][j] == 0) dfs(i,j,1);
		}
	}
	cout << ans<<"\n";
	return 0;
}