[BOJ] 백준 [1937] 욕심쟁이 판다 JAVA

이 문제는 DFS + DP 문제이다. 여기서 DP는 최대 생존가능일 수를 기록.

기본적으로 , 입력을 map으로 받았을때, 다음 이동해야 하는 방향의 값이 지금의 값보다 더 커야한다.

즉 , map[y][x] < map[nextY][nextX] 가 성립 해야 한다.

 

그리고 탐색했던곳을 중복탐색하는 것을 막기위해 메모이제이션 기법으로 dp를 바로 반환해주는것이 핵심이다.

그렇지 않으면 시간초과 발생.

if(dp[y][x] != 1)
 return dp[y][x];

 

dfs로 탐색했을때 , 현재 기록된 생존가능일 수 보다 더 오래 살 수 있으면 갱신. 

dp[y][x] = Math.max(dfs(nextX,nextY)+1,dp[y][x]); 

 

처음에 바로 떠 올리기엔 쉽지 않은 문제이다.

 

import java.util.*;
import java.io.*;
import java.time.LocalDateTime;
 
 
public class Main{
 
    static int[][] map; 
    static int[][] dp; 
    //dx dy로 map탐색 방향 정의
    static int[] dx= {0,0,1,-1}; 
    static int[] dy= {1,-1,0,0};
    static int size, max=1;
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        size = Integer.parseInt(br.readLine()); // 맵 크기
        map = new int[size+1][size+1]; 
        dp = new int[size+1][size+1];
        for(int i=1; i<=size; i++)
        {
            String[] input = br.readLine().split(" ");
            for(int j=1; j<=size; j++) {
                map[i][j] = Integer.parseInt(input[j-1]);
                dp[i][j] = 1;
            }
        }
        
        for(int i=1;i<=size;i++)
        {
            for(int j=1;j<=size;j++)
                dfs(i,j);
        }
        System.out.println(max);
        
    }
    static int dfs(int x,int y)
    {
 
        if(dp[y][x] != 1)
            return dp[y][x];
        
        for(int i=0; i<dx.length;i++)
        {
            int nextX = x+dx[i];
            int nextY = y+dy[i];
            
            
            if(isRange(nextX,nextY) && map[nextY][nextX] > map[y][x])
            {
                dp[y][x] = Math.max(dfs(nextX,nextY)+1,dp[y][x]);
            }
        }
        max = Math.max(dp[y][x],max);
        return dp[y][x];
    }
    static boolean isRange(int x,int y)
    {      
        return x>0 && y>0 && x<=size && y<=size ? true : false;
    }
 
}