백준 1937: 욕심쟁이 판다 [골드 Ⅲ / Java]

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

1937번: 욕심쟁이 판다

---

 

• 알고리즘 : DFS + DP
• 풀이 날짜 : 과거, 2023.06.11. 리뷰

 

 

< 풀이 설명 >

판다 일러스트 출처 :

https://kor.pngtree.com/freepng/hand-drawn-cute-panda-eating-bamboo-leaves-illustration_4563517.html 

대나무 일러스트 출처 : 

https://www.logoyogo.com/downloads/%EB%8C%80%EB%82%98%EB%AC%B4-%EC%95%84%EC%9D%B4%EC%BD%98-%EB%A1%9C%EA%B3%A0-%EC%9D%BC%EB%9F%AC%EC%8A%A4%ED%8A%B8-ai-%EB%AC%B4%EB%A3%8C-%EB%8B%A4%EC%9A%B4%EB%A1%9C%EB%93%9C/

출처 : 더보기

 

 

판다는 현재 지역에서 먹은 대나무 개수보다 다음 지역에서는 더 많은 대나무를 먹어야 한다 (7개 ▶ 10개).

 

 

 

처음에 DFS로 동, 서, 남, 북 방위로 탐색했을 때 현재보다 더 많은 대나무 지역쪽으로 재귀를 해주었다.

DP 값에는, 적은 수 대나무 지역부터 방문한 지역 개수를 넣어주었다.

 

 

하지만 어떤 지역에 도착하는 방법에는 여러 가지일 수도 있다.

위 그림에서 보면 11 (1, 1) 로 가는 방법에는, 9 (0, 1)에서 가는 방법, 1 (1, 0)에서 가는 방법, 5 (1, 2)에서 가는 방법으로 3가지가 있다.

 

따라서 어떤 지역을 한 번 탐색했다고 visited 처리하지 않고(못 하고), 대나무 개수 비교로 탐색 여부를 판단했다.

 

 

하지만 다음과 같은 경우에 시간 초과가 날 수 있다.

 

 

visited 처리를 해줄 수가 없으니,

갱신되는 족족 이미 DFS 탐색을 마친 path가 다시 DFS 탐색이 진행된다.

문제에서 숲의 최대 크기가 500 * 500 으로,

시간 복잡도는 약 (500 * 500) * (500 * 500 * 4) 까지 나올 수 있으므로,

문제 시간 제한 조건인 2초 (Java 기준 약 2억 번 계산) 을 초과하게 된다.

 

 

 

 

따라서 다른 사람 코드를 참고하여 수정했다.

 

현재에서 갈 수 있는 방향으로 탐색하는 것이 아니라,

현재까지 올 수 있는 방향으로 탐색한다.

거꾸로 업데이트 하며 오는 것이다.

 

 

현재 지역까지 올 수 있는 가지 수를, 선수 지역을 재귀로 먼저 업데이트를 마친 후, 그제서야 저장하면 된다.

재귀함수를 변수로 사용하는 방식이다.

 

 

 

본인이 다음 문제를 풀었던 방식과 동일하다.

[백준/골드] - 백준 1005: ACM Craft [골드 Ⅲ]

 

 

 

< 코드 >

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, max;
    static int[][] bamboos;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        bamboos = new int[N][N];
        for (int r = 0; r < N; ++r) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; ++c)
                bamboos[r][c] = Integer.parseInt(st.nextToken());
        }


        // DP[][]: 거꾸로 올 때, 해당 인덱스까지 이동할 수 있는 최댓값
        dp = new int[N][N];
        max = 0;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c)
                max = Math.max(max, dfs(r, c));
        }

        System.out.println(max);
    }

    private static int dfs(int r, int c) {
        /*
         역방향 : 이미 갱신된 지역은 바로 그 값을 리턴한다.
         정방향 : 해당 인덱스까지 올 수 있는 루트가 또 있다. 그래서 visited 처리 해주면 안 된다.
         그럼, 해당 인덱스 시작이 아니라, 해당 인덱스가 마지막일 때 올 수 있는 방향으로 생각하자.
         */

        // visited 여부 (Base case)
        if (dp[r][c] != 0) return dp[r][c];

        // 기본 값
        dp[r][c] = 1;

        for (int k = 0; k < 4; k++) {
            int new_r = r + dir[k][0];
            int new_c = c + dir[k][1];
            if (new_r >= N || new_r < 0 || new_c >= N || new_c < 0) continue;

            if (bamboos[new_r][new_c] > bamboos[r][c])
            /** !!!!! 재귀함수 이용해서 돌아오면서 갱신 !!!!! **/
                dp[r][c] = Math.max(dp[r][c], dfs(new_r, new_c) + 1);
        }

        return dp[r][c];
    }

}