[백준 1937] 욕심쟁이 판다

문제

1937번: 욕심쟁이 판다

1937번: 욕심쟁이 판다

풀이

이 문제는 DFS의 개념으로 풀이는 가능하지만 DFS만 사용한다면 시간초과로 인해 통과하지 못한다. DFS로 풀며 시간복잡도를 더 줄여야 통과가 가능한 문제이다.

 

그렇다면 어떻게 더 줄여야 할까?

 

바로 DP를 이용하면 된다. DP를 사용해서 이미 탐색한 부분이 있다면 진행하지 않고 탐색된 부분의 값을 사용하는 것이다.

코드를 예시로 보자.

 

if (dp[x][y] > 0) {
    return dp[x][y];
}

위 코드는 dp 배열의 인덱스에 0 이상의 값이 있다면 해당 값을 반환한다. 0 이상이라는 말은 이미 현재 지점을 기점으로 dfs를 진행한 결과 값이 저장되었다는 말이므로, 다시 진행할 필요없이 해당 값을 사용하면 된다.

 

if (map[dx][dy] > map[x][y]) {
    dp[x][y] = Math.max(dp[x][y], dfs(dx, dy) + 1);
}

dp에 이미 존재하는 값을 반환했다면, 위 코드의 dfs(dx, dy) 에 반환될 것이고 거기서 1을 더해준다. 그리고 현재 dp의 인덱스에 저장된 값과 비교해서 나온 더 큰 값을 현재의 dp에 다시 할당한다.

이렇게 dfs를 진행하게 되면 해당 지점에서 가장 많은 칸의 값이 저장된다.

코드

public class Main {

    static int[] X = {-1, 0, 1, 0};
    static int[] Y = {0, 1, 0, -1};
    static int[][] map;
    static int[][] dp;
    static int n;

    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];

        StringTokenizer st;
        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());
            }
        }

        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);
    }

    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 dx = x + X[i];
            int dy = y + Y[i];

            if (dx < 0 || dy < 0 || dx >= n || dy >= n) {
                continue;
            }

            if (map[dx][dy] > map[x][y]) {
                dp[x][y] = Math.max(dp[x][y], dfs(dx, dy) + 1);
            }

        }
        return dp[x][y];
    }
}