[BOJ] 백준 1937번 : 욕심쟁이 판다 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

문제

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

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

 

풀이

DFS와 DP를 사용하여 풀 수 있는 문제였습니다. 저는 문제만 읽고, "오 이거는 빼박 DFS 돌리면서 다 검사하면 되겠네"하고 돌렸다가 15퍼에서 시간초과 컷 당했습니다. 그래서 중복되는 부분을 배제하기 위해서 DP를 사용해야했습니다. 한 번 갔던 경로는 메모이제이션을 이용해서 저장해놓고, 그 영역을 탐색하려고할 때는 저장해 둔 값을 반환하면 됩니다.

저는 dp를 2차원 배열로 선언하였고, (x, y) 좌표에서 판다가 출발하면 z년 동안 생존한다라는 의미를 갖고 있습니다.

그리고 매 좌표마다 항상 최댓값을 저장하기때문에 이미 저장된 영역에 도달했을 시, 그 dp 값을 이용하면 됩니다.

가령, 대나무 숲이 아래와 같이 주어져있다고 가정합시다.

 

 

그리고 만약, 판다가 (0, 0)부터 출발한다면, 2 -> 3 -> 4로, 이동할 수 있으므로 총 3년을 생존할 수 있습니다.

따라서, dp[0][0] = 3이라고 저장할 수 있게 되죠.

그렇다면, 판다가 (1, 0)부터 출발한다면 어떨까요?

1 -> 2 -> 3 -> 4로 이동할 수 있으므로 총 4년을 생존할 수 있습니다. 하지만, dp[0][0] = 3이 저장되어있으므로 dp[1][0] = dp[0][0] + 1만 취해주면 됩니다.

 

아래는 위 풀이 과정을 소스코드로 옮긴 것입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int[] rangeX = { -1, 0, 1, 0 };
    static int[] rangeY = { 0, 1, 0, -1 };
    static int N;
    static int[][] map; // 대나무 숲
    static int[][] dp;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
            }
        }
 
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ans = Math.max(ans, DFS(i, j));
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static int DFS(int x, int y) {
        // dp에 저장된 값이 있을 경우 그 값을 반환.
        if (dp[x][y] != 0) {
            return dp[x][y];
        }
        
        // 판다가 대나무 숲에서 최소한 1년은 살 수 있으므로
        // dp[x][y] = 1로 초기화 할 수 있음.
        dp[x][y] = 1;
 
        int dx, dy;
        // 상하좌우 검사.
        for (int i = 0; i < 4; i++) {
            dx = x + rangeX[i];
            dy = y + rangeY[i];
            
            // 범위에서 벗어났을 경우 continue.
            if (dx < 0 || dy < 0 || dx >= N || dy >= N) {
                continue;
            }
            
            // 현재 대나무 숲보다 더 많은 양의 대나무가 있는 경우.
            if (map[x][y] < map[dx][dy]) {
                // 상하좌우 중에서 가장 오랫동안 생존할 수 있는 기간을 계산한다.
                dp[x][y] = Math.max(dp[x][y], DFS(dx, dy) + 1);
                DFS(dx, dy);
            }
        }
        return dp[x][y];
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.