백준 BOJ 1937 - 욕심쟁이 판다

DP + DFS

https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

dp[x][y] 를

(x,y)에서 판다가 먹기 시작할때 지날수 있는 위치의 최대값으로 만들어주면

쉽게 해결할 수 있다.

이 dp[x][y]를 구하기 위해서는 주변 네칸을 탐색 후 dp[nx][ny]가 구해지지 않았다면 이 또한 구해주는

DFS를 이용하면 AC를 받을 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

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

int arr[567][567] = {0};
int dp[567][567] = {0};
int n;

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

int main(){
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> arr[i][j];
		}
	}
	
	int ans = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			ans = max(ans, f(i,j));
		}
	}
	cout << ans;
	return 0;
}