[PS] 백준1937 : 욕심쟁이 판다(Java)

문제

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

1937번: 욕심쟁이 판다

---

풀이

DP를 활용한 완전탐색

첫번째 접근법 (BFS)

각 격자별로 BFS를 수행하면서 DP 메모이제이션을 수행.

다음 탐색좌표에 대한 최장길이 DP값이 있다면 해당 부분문제 해를 이용하여 현재 최장길이를 구하는 식으로 풀이.

두번째 접근법 (DFS)

첫번째 접근에서 메모리초과가 발생하여 DFS로 변경

로직자체는 동일

각 좌표마다 DFS를 수행하면서 다음 나아가는 좌표에 대해 메모이제이션 해놓은 값이

1. 있다면 해당값을 이용해 해를 구함
2. 없다면 다음 좌표에 대해 다시 재귀 호출

 

---

첫번째 접근법 소스코드

//BOJ_1937 욕심쟁이 판다
public class Main {
    static int N, res;
    static int[] dx = new int[]{1, -1, 0, 0};
    static int[] dy = new int[]{0, 0, 1, -1};
    static int[][] map, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dp[i][j] = dfs(i, j);
                res = Math.max(res, dp[i][j]);
            }
        }

//        for(int i=0; i<N; i++) System.out.println(Arrays.toString(dp[i]));

        System.out.println(res);
    }

    private static int bfs(int r, int c) {
        //기저조건
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{r, c, 1});
        int max = 1;

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            max = Math.max(max, cur[2]);

            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

                if (map[cur[0]][cur[1]] < map[nx][ny]) {
                    if (dp[nx][ny] != Integer.MAX_VALUE) {
                        max = Math.max(max, cur[2] + dp[nx][ny]);
                    } else q.offer(new int[]{nx, ny, cur[2] + 1});
                }
            }
        }
        return max;
    }
}

두번째 접근법 소스코드

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

//BOJ_1937 욕심쟁이 판다
public class Main {
    static int N, res;
    static int[] dx = new int[]{1, -1, 0, 0};
    static int[] dy = new int[]{0, 0, 1, -1};
    static int[][] map, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dp[i][j] = dfs(i, j);
                res = Math.max(res, dp[i][j]);
            }
        }

        System.out.println(res);
    }
    private static int dfs(int r, int c) {
        //동작
        for(int i=0; i<4; i++) {
            int nx = r + dx[i];
            int ny = c + dy[i];
            if(nx<0 || ny<0 || nx>=N || ny>=N) continue;

            if(map[r][c] < map[nx][ny]) { //다음 진행방향으로 나아갈 수 있는 경우
                if(dp[nx][ny] == 0) { //다음 진행방향이 탐색되지 않은 좌표라면
                    dp[r][c] = Math.max(dp[r][c], dfs(nx, ny)+1);
                }
                else { //이미 탐색된 좌표일 경우 해당 좌표의 dp값+1
                    dp[r][c] = Math.max(dp[r][c], dp[nx][ny]+1);
                }
            }
        }
        if(dp[r][c] == 0) return 1;
        return dp[r][c];
    }
}

 

 

---

정리

백준 욕심쟁이 판다 제출 결과

해당 문제에 대해서 BFS와 DFS를 두 개를 시도해보면서 각각의 방식에 대해 탐색횟수에 대해서 추가로 조사해본 결과

BFS 로직 탐색횟수

DFS 로직 탐색횟수

• BFS에서는 수행횟수 탐색을 위해 큐에서 꺼낼 때 마다 cnt값을 증가시켰고 결과 도출까지 총 43번의 좌표탐색이 이루어진걸 알 수 있음.
• DFS에서는 수행횟수 탐색을 위해 재귀호출이 될 때 마다 cnt값을 증가 → 결과 총 27번의 좌표탐색이 이루어짐.

욕심쟁이 판다의 문제에 관해서는 얼마나 DP값을 활용하냐에 따라서 수행횟수가 다를 수 있을텐데 위 결과로 미루어보아 DFS의 경우가 훨씬 DP값을 더 잘 활용할 수 있는 방식이라 볼 수 있음.

 

BFS의 경우 각 좌표에 대해 탐색을 진행한 후 해당 좌표의 값만 DP 갱신이 이루어지는데

DFS는 각 좌표에 대해 탐색을 진행할 때 거쳐가는 좌표들에 대해서도 DP 갱신이 이루어지기 때문에 다음 탐색에 있어 활용할 수 있는 값이 더 많아질 수 밖에 없음

 

---

추가적으로 BFS로 제출했을 때 34% 메모리 초과가 발생한 케이스에 대한 이유에 대해 생각해보며 한가지 테스트를 해보았는데

10
14 9 12 10 8 4 10 12 11 29
1 11 5 4 8 4 10 12 11 29
7 15 2 13 8 4 10 12 11 29
14 9 12 10 8 4 10 12 11 29
1 11 5 4 8 4 10 12 11 29
7 15 2 13 8 4 10 12 11 29
14 9 12 10 8 4 10 12 11 29
1 11 5 4 8 4 10 12 11 29
7 15 2 13 8 4 10 12 11 29
6 3 16 8 8 4 10 12 11 29

 

위와 같은 예제입력에 대해 일반적인 방문체크 배열을 활용하여 탐색하는 BFS의 각 while문 마다 큐 사이즈를 출력하는 프로그램을 돌려본 결과

BFS 큐 사이즈 출력 결과

 

위와 같이 (10,10) 사이즈에 대해 최대 14의 큐 사이즈를 가지는 경우를 확인할 수 있는데

욕심쟁이 판다 문제의 경우 N이 최대 500까지 주어지기 때문에 최악 경우 큐 사이즈가 256MB 이상의 크기를 충분히 가질 수 있기에 메모리 초과가 발생했다고 볼 수 있을 것 같음

---

 

이번 문제를 통해 BFS와 DFS의 차이를 어느정도 알 수 있었고, 시간이 된다면 추가적으로 2차원 배열 최장길이 탐색에 있어 DFS가 왜 유리한지에 대해 로직을 뜯어보며 검증할 수 있는 시간을 가질 수 있으면 함.