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

 

문제

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	256MB	25266	8068	5243	29.870%

문제

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

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

입력

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

출력

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

 

풀이

판다의 이동은 백준1520번 내리막길과 비슷하다.

DFS를 통해 모든 점에서 판다의 이동을 시작하여 그 값을 계산한다.

이때 그냥 그렇게만 한다면 시간복잡도는 $O(V^2(V+E))$로 엄청 크다.

DFS를 모든 점에서 반복해서 수행하므로 -> 각각의 좌표별 결과를 DP로 유지하면 된다.

판다가 내리막길에서만 이동가능하기 때문에, 역행할 일은 없으므로 굳이 방문한 노드를 체크해주지는 않아도 된다.

문제의 조건에 따라 대나무가 1,000,000 보다 작거나 같은 자연수이기 때문에 최대로 움직일 수 있는 횟수는 1,000,000번이라 할 수 있다.

막연하게 재귀 스택이 못버틸 줄 알았지만 재귀로도 가능하였다.

구체적인 내용은 질문글을 참조하였는데

재귀 호출되는 함수에 선언되는 지역 변수, 함수 호출 스택 -> 한 호출별로 메모리에 영향 (대략 수십 바이트 이하)

백준에서는 64MB 정도까지 스택을 허용하여 여유로움

처음에는 BFS를 사용해서 풀어보려고 했다.

하지만 BFS를 사용하면 다음의 문제가 발생하여 실패한다.

DP를 활용하여 이미 값이 있으면 안 하는 경우 -> 더 클 수 있는 경우에 패스해버림

그렇다면 값이 더 크거나 같은 경우로 포함 -> 시간초과

 

코드

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

public class Main {

    static int n;
    static int map[][];

    static int countMap[][];

    static int[] xMove = {1, 0, -1, 0};
    static int[] yMove = {0, -1, 0, 1};


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

      st = new StringTokenizer(br.readLine());
      n = Integer.parseInt(st.nextToken());

      map = new int[n][n];
      countMap = 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 answer = 0;
      for(int i=0; i<n; i++) {
          for(int j=0; j<n; j++) {
              answer = Math.max(answer, DFS(new Point(i,j)));
          }
      }
      System.out.println(answer);
   }

   public static int DFS(Point startPoint){

       if(countMap[startPoint.y][startPoint.x] != 0) 
           return countMap[startPoint.y][startPoint.x];

       int count = 0;
       int currentVal = map[startPoint.y][startPoint.x];

       //4방향 체크
       for(int i=0; i<4; i++){
           int newY = startPoint.y + yMove[i];
           int newX = startPoint.x + xMove[i];

           if(newX >= 0 && newX < n && newY >= 0 && newY < n) {
               if(map[newY][newX] > currentVal) {
                   count = Math.max(count, DFS(new Point(newX, newY)));
               }
           }
       }
       return countMap[startPoint.y][startPoint.x] = count +1;

   }
}

class Point{
    public int x;
    public int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

결과