백준 1937 욕심쟁이 판다 (Java)

1. 문제 링크

1937번: 욕심쟁이 판다

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. dfs 탐색으로만 하려다 크기가 큰 것 같아 이동 칸을 저장하기 위한 dp까지 함께 사용했다.

2. 모든 칸에서 dfs 탐색을 진행한다.

    2-1. dp가 이미 채워져 있을 경우, 그 값을 반환한다.

    2-2. 첫 방문일 경우, 한 칸을 뜻하는 1을 저장한다.

    2-3. 사방 탐색을 하면서 지금보다 더 많은 대나무가 있는 곳으로 이동한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N, map[][], result, dp[][];
	static int[] dx = {0,0,-1,1}, dy = {-1,1,0,0};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		dp = new int[N][N]; //최대 이동 칸 저장
		for(int i=0;i<N;i++) {
			String[] split = br.readLine().split(" ");
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				result = Math.max(result, dfs(i, j));
			}
		}
		
		System.out.println(result);
	}
	
	private static int dfs(int i, int j) {
		if(dp[i][j]!=0) {
			return dp[i][j];
		}
		
		dp[i][j] = 1; //첫 방문 시
		
		for(int d=0;d<4;d++) {
			int x = i + dx[d];
			int y = j + dy[d];
			//더 큰 곳만 가니까 굳이 방문 처리할 필요 없음
			if(x>=0 && x<N && y>=0 && y<N && map[x][y]>map[i][j]) {
				dp[i][j] = Math.max(dp[i][j], dfs(x, y)+1);
			}
		}
		return dp[i][j];
	}
}