[DFS/DP] 백준 - 1937번: 욕심쟁이 판다 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

1937번: 욕심쟁이 판다

 

 

위 문제는 판다가 i, j 좌표부터 대나무를 먹는데 이때 다른 대나무를 먹기 위해선 기존에 먹던 대나무 숫자보다 많아야 한다.

근데 처음에 DFS로 풀다 보니 시간 초과가 계속 떴었다..

 

그래서 질문 검색을 보니 DP를 활용해야 했던 것이었다.

DFS를 돌면서 DP도 동시에 해줘, DP에서 가장 높은 값을 가져와야 한다.

 

코드

import java.util.Scanner;

public class Main {
    static int[][] map;
    static int[][] dp;
    static int n;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        map = new int[n][n];
        dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count = Math.max(count, dfs(i, j));
            }
        }

        System.out.println(count);
    }
    
    private 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 nowX = x + dx[i];
            int nowY = y + dy[i];

            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < n) {
                if (map[x][y] < map[nowX][nowY]) {
                    dp[x][y] = Math.max(dp[x][y], dfs(nowX, nowY) + 1);
                }
            }
        }

        return dp[x][y];
    }
}

 

위 코드를 실행해보면 DP에는 

좌) 예제 입력, 우) DP 결과

DP에는 이렇게 쌓이게 된다.

먹는 예시

1. 4 -> 5 -> 11 -> 15
2. 2 -> 5 -> 11 -> 15
3. 3 -> 6 -> 7 -> 15

순으로 되기 때문에 최대 4번을 먹을 수 있다는 결론이 나온다!

 

골드 4에서 3으로 넘어가니 다른 알고리즘과 결합이 되었다..