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

[백준]1937: 욕심쟁이 판다

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

풀이

처음에는 DFS만 사용해서 풀었더니 시간초과가 났다! DP와 DFS를사용해 메모이제이션 하면서 풀어야 한다.

 

dp에 저장되는 값은 다른 위치에서 현재 위치까지 이동할 수 있는 거리 중 최대값을 의미한다. 그러므로 이동하면서 계속 갱신해 주어야 한다.

 

즉 현재위치가 x, y이고 이동할 위치가 nx, ny라고 할 때

dp[x][y] = dp[nx][ny] + 1과 dp[x][y]중의 최댓값이 된다.

 

코드

import java.util.*;
 
public class Main {    
 
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static int max = 0;
    static int[][] node;
    static int[][] dp;
    static int n;
    
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        node = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                node[i][j] = scan.nextInt();
            }
        }
        
        dp = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                max = Math.max(dfs(i, j), max);
            }
        }
        System.out.println(max);
    }
    
    public static int dfs(int x, int y) {
        if(dp[x][y] != 0) return dp[x][y];
        
        dp[x][y] = 1;
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if(node[nx][ny] > node[x][y]) {
                    dp[x][y] = Math.max(dp[x][y],  dfs(nx, ny) + 1);
                }
            }
        }
        return dp[x][y];
    }
}