[BOJ] 1937. 욕심쟁이 판다

dp와 dfs를 같이 활용한 문제이다.

저번에 풀었던 1520번 내리막길과 비슷한 문제이다. 마찬가지로 dfs를 도는데 최대 n의 크기가 500이 되므로 중간에 이차원 dp 배열을 통해 메모이제이션을 활용하는 전략을 사용했다. 이 문제도 마찬가지로 dp 이차원 배열을 -1로 초기화 시키고 dfs 의 반환값을 dp[i][j]로 반환하면서 dp값을 찾는 방식이다. 다만 이 문제에서 유의할점은 각 위치에서의 최대값을 찾는 것이기 때문에 dp를 갱신할때 dfs+1 (현재포함)한 값과 비교하여 최대값을 찾는 방식으로 구현해야 한다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_1937_욕심쟁이판다 {
    static class Pos {
        int i, j;
 
        public Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
 
    static int[] di = {-1, 0, 1, 0};
    static int[] dj = {0, 1, 0, -1};
 
    static int[][] map;
    static int[][] dp;
 
    static int N;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
 
        map = new int[N][N];
        dp = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
 
        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                answer = Math.max(answer, dfs(i, j));
            }
        }
 
        System.out.println(answer);
    }
 
    static int dfs(int i, int j) {
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
 
        dp[i][j] = 1;
 
        for (int dir = 0; dir < 4; dir++) {
            int nextI = i + di[dir];
            int nextJ = j + dj[dir];
 
            if (nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= N) {
                continue;
            }
 
            if (map[i][j] < map[nextI][nextJ]) {
                dp[i][j] = Math.max(dp[i][j], dfs(nextI, nextJ) + 1);
            }
        }
 
        return dp[i][j];
    }
}