[백준] 1937. 욕심쟁이 판다

dp와 dfs로 풀었다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ1937_욕심쟁이_판다 {
	static int N,K;
	static int[][] map,result;
	//상하좌우
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		K=0;
		map = new int[N][N];
		result = new int[N][N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//point 하나하나 접근했을 경우의 max값 알아내기
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				K = Math.max(dfs(i,j),K);
			}
		}
		System.out.println(K);
	}
	
	
	private static int dfs(int x, int y) {
		//4방탐색하면서 값을 찾아주기
		//결과를 result에 넣기
		if(result[x][y]!=0) {
			return result[x][y];
		}
		
		result[x][y]++;
		
		// 범위 안에 있을 경우 && 만약 현재 위치의 대나무 양보다 그 다음 방향에 대나무가 많을 경우만 이동 
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			
			if(isValid(nx,ny) && map[x][y]<map[nx][ny]) {
				result[x][y] = Math.max(result[x][y], dfs(nx,ny)+1);
			}
		}
		return result[x][y];
	}

	private static boolean isValid(int nx, int ny) {
		return nx>=0 && nx<N && ny>=0 && ny<N;
	}

}