[BOJ] 1937 - 욕심쟁이 판다 JAVA

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

문제

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n*n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 오래 살려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 최대한 살 수 있는 일수(K)를 출력한다.

예제 입력 1

4

14 9 12 10

1 11 5 4

7 15 2 13

6 3 16 8

예제 출력 1

4

 

 

 

 

 

 

 

풀이 1. (틀린 코드 - 메모리 초과)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int n, ans;

    static int[][] map = null;
    static int[][][] dp = null;  // dp[r][c][dept] = (r, c)에 dept번째로 방문했을 때 가질 수 있는 최장경로
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1 ,1};

    public static void dfs(int r, int c, int dept) {
        dp[r][c][dept] = 0;
        for(int i = 0; i < 4; i++) {
            int nr = r + rArr[i];
            int nc = c + cArr[i];
            if(-1 < nr && nr < n && -1 < nc && nc < n && map[r][c] < map[nr][nc]) {
                if(dp[nr][nc][dept+1] == -1) {
                    dfs(nr, nc, dept+1);
                }
                dp[r][c][dept] = Math.max(dp[r][c][dept], dp[nr][nc][dept+1]);  // 상하좌우 중 최대값
            }
        }
        dp[r][c][dept] += 1;  // 자기 자신에 대한 값 추가
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        dp = new int[n][n][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());
            }
        }

        // dp 초기화
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dfs(i, j, 0);
                ans = Math.max(ans, dp[i][j][0]);
            }
        }
        System.out.println(ans);
    }
}

로직은 맞지만 메모리 초과가 나는 코드.

 

매번 풀기 전에 시간, 용량 계산부터 해보자고 다짐하면서도 그걸 실행에 옮기기가 쉽지 않다.

n제한이 dp를 3차원 배열로 사용할 경우 500^4 칸의 int 배열이 필요한데 이는 약 250GB의 용량.. 메모리 제한 256MB를 넘어가도 한참을 넘어간다.

 

로직은 이랬다.

 

dp[r][c][dept] = (r, c)를 dept번째로 방문했을 때 더 나아갈 수 있는 최장경로.

(r, c)에서 상하좌우의 (nr, nc)에 대해 dp[nr][nc][dept+1]의 값 중 최대값을 더한 후 자신에 대한 값 1을 추가하는 것이다.

 

아래 링크의 문자판 문제와 비슷한 방식으로 떠올린 풀이였다.

codeung.tistory.com/216?category=449370  

 

로직은 맞긴 하지만 어쨌든 틀린 코드..

 

3차원 배열의 구조를 유지하면서 dp의 용량을 줄일 수 있는 방법을 고민해보았지만 그런 건 없다.

2차원 배열로 다시 풀어야 한다.

 

 

 

 

 

 

풀이 2. (정답 코드)

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int n, ans;

    static int[][] map = null;
    static int[][] dp = null;  // dp[r][c] = (r, c)를 시작점으로 하여 나아갈 수 있는 최장경로
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1 ,1};

    public static void dfs(int r, int c) {
        dp[r][c] = 0;
        for(int i = 0; i < 4; i++) {
            int nr = r + rArr[i];
            int nc = c + cArr[i];
            if(-1 < nr && nr < n && -1 < nc && nc < n && map[r][c] < map[nr][nc]) {
                if(dp[nr][nc] == -1) {
                    dfs(nr, nc);
                }
                dp[r][c] = Math.max(dp[r][c], dp[nr][nc]);  // 상하좌우 중 최대값
            }
        }
        dp[r][c] += 1;  // 자기 자신에 대한 값 추가
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        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());
            }
        }

        // dp 초기화
        for(int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dfs(i, j);
                ans = Math.max(ans, dp[i][j]);
            }
        }
        System.out.println(ans);
    }
}

 

3차원 배열이 dept부분만 없애서 간단하게 해결했다.

 

3차원 배열은 메모리 초과, 2차원으로 처리해야 한다 -> 2차원으로 줄여도 좌표에 대한 정보는 반드시 포함해야 한다 -> dp[r][c] 에다 뭘 담지? -> (r, c)을 시작점으로 나아갈 수 있는 최장경로

 

굳이 해당 좌표에 몇 번째로 방문하는지 순서까지 메모이제이션 할 필요가 없었다.

어차피 (r, c)에서의 최장경로 = max(상하좌우의 각 (nr, nc)에서의 최장경로) + 1 이니까.

앞선 메모리 초과 코드에서 dp[r][c][0]을 dp[r][c]로 사용한다는 것.