백준_욕심쟁이판다_1937

문제 링크

조건

•  n  : 대나무 숲 크기, 1~500 이하
• 현재 칸보다 대나무가 더 많은 칸으로만 이동 가능

 

접근 방법

• 메모이제이션 활용
  • memo 배열에 현재 칸(i, j)에서 출발했을 때 최대 몇일 살아남을 수 있는지 저장하며 시간을 단축

 

솔루션

public class Main_1937_욕심쟁이판다 {
	static int N;
	static int[][] map, memo;
	static int K;//판다가 살아남을 수 있는 day 수
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine().trim());
		
		map = new int[N][N];
		memo = new int[N][N];//(i,j)에서 출발했을 때 최대 몇일 살아남을 수 있는지 저장
		
		for(int i = 0; i < N; i++) {//map에 대나무 개수 입력
			StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		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+1);
		
	}
	
	private static int dfs(int r, int c) {
		if(memo[r][c] > 0) return memo[r][c];//메모 기록이 있다면 return
		int nr,nc;
		
		int max = 0;
		for(int i = 0; i < 4; i++) {
			nr = r + dr[i];
			nc = c + dc[i];
			
			//범위에서 벗어나거나 || 대나무 수가 현재 있는 지점보다 적거나
			if(nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] <= map[r][c]) continue;

			max = Math.max(max, dfs(nr,nc) + 1);
		}
		
		return memo[r][c] = max;//사방 탐색 후 최대값 저장
	}
}

 

리뷰

• 처음에는 memo배열에 현재 칸부터 dfs 돌면서 depth를 저장함 => 시간초과
  • dfs으로 최대 값을 구하는 경우, 끝까지 가봐야 알기 때문에 시간초과가 날 가능성이 높음
• memo 배열에 현재 칸에서 출발했을 때 최대 몇일 살아남을 수 있는지를 저장해야 함 => 메모이제이션