백준 1937. 욕심쟁이판다 :: 돼지개발자

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

"DP"

DP를 이용한 문제이다. top down 방식을 사용한다. 재귀를 할 때, 리턴 값이 있는 경우 처리를 잘해 주어야 겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    static int n;
    static int[][] map;
    static int[][] dp;
    static int max;
    static int[] dx = {0,0,1,-1};
    static int[] 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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(dp[i], -1);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, solve(i,j));
            }
        }
        
        System.out.println(max);
    }
    
    static int solve(int x, int y) {
        if(dp[x][y] != -1) return dp[x][y];
        
        int temp = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x +dx[i];
            int ny = y +dy[i];
            
            if(!isRange(nx, ny) || map[x][y] >= map[nx][ny]) 
                continue;
            
            temp = Math.max(temp, solve(nx,ny) +1);
        }
        return dp[x][y] = temp;
    }
    
    static boolean isRange(int x, int y) {
        if(x < 0 || x >= n || y < 0 || y >= n) return false;
        return true;
    }
}