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

1. 문제

1937번: 욕심쟁이 판다

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

---

2. 풀이

정적 변수

int N	숲 크기
int[][] info	대다무 숲 정보
int[][] dp	dp[i][j]에서 출발했을 때의 최대 이동 횟수 저장
int[][] deltas	사방탐색 이동값

 

Main

info에 숲 정보를 모두 저장한다.

dp 배열을 생성한 후 하나씩 탐색한다.

dp[i][j]에 dfs(i,j)를 저장하고, MAX와 dp[i][j]와 비교해서 더 큰 값을 MAX에 저장한다.

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

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

   System.out.println(MAX);
}

 

DFS

이미 dp[i][j]에 저장된 값이 있다면 return dp[i][j]한다.

max는 dp[i][j]이후의 경로 길이다. 현재위치 [i][j]에서 사방탐색하면서 갈 수 있는 위치라면 dfs(ni,nj)를 호출한다.

dfs(ni,nj)와 max값을 비교해서 더 큰 값을 max에 저장한다.

마지막으로 dp[i][j]에 1 + max를 저장하고 그대로 반환한다. 1을 더하는 이유는 현재위치의 경로횟수를 포함하기 위해서다.

private static int dfs(int i, int j){
   if(dp[i][j]!=0) return dp[i][j];

   int ni,nj, max = 0;
   for(int[] d:deltas){
      ni = i+d[0];
      nj = j+d[1];
      if(ni<0||nj<0||ni>=N||nj>=N||info[ni][nj]<=info[i][j]) continue;
      max = Math.max(max,dfs(ni,nj));
   }
   return dp[i][j] = 1 + max;
}

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_1937_욕심쟁이판다 {
   static int[][] info, dp;
   static int N;
   static int[][] deltas = {{1,0},{0,1},{0,-1},{-1,0}};
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      info = new int[N][N];
      StringTokenizer st;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         for(int j=0;j<N;j++){
            info[i][j] = Integer.parseInt(st.nextToken());
         }
      }

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

      System.out.println(MAX);
   }

   private static int dfs(int i, int j){
      if(dp[i][j]!=0) return dp[i][j];

      int ni,nj, max = 0;
      for(int[] d:deltas){
         ni = i+d[0];
         nj = j+d[1];
         if(ni<0||nj<0||ni>=N||nj>=N||info[ni][nj]<=info[i][j]) continue;
         max = Math.max(max,dfs(ni,nj));
      }
      return dp[i][j] = 1 + max;
   }
}

---

3. 결과