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

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

1. 문제 설명

 

n*n 크기의 대나무 숲이 있을 때 판다가 어떤 지역에서 대나무를 먹는다. 그리고 그다음 지역은 현재 지역보다 대나무가 많이 있는 지역이어야 한다. 그렇지 않으면 판다는 죽는다고 할 때 판다의 최대한 오래 살 수 있는 일수를 구하는 문제이다.

 

2. 풀이

 

시작 위치가 정해져 있지 않기에 dfs로 곧장 푸는 것보다는 dfs+dp로 푸는 것이 효율적이다.

 

현재 위치에서 상, 하, 좌, 우 중 현재보다 대나무가 더 많은 곳들을 탐색하여 현재 위치에서 시작한다면 가장 오래 살 수 있는 일수를 구하였다. 그리고 이를 cache 배열에 저장하고 사용하는 방식으로 풀어서 중복 계산을 제거하였다.

 

시간 복잡도는 O(N^2)이다.

 

3. 코드

 

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    public static int N;

    public static int[][] forest=new int[500][500];

    public static int[][] cache = new int[500][500];

    public static int[][] plus = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());


        for (int x = 0; x < N; x++) {
            StringTokenizer temp = new StringTokenizer(br.readLine());

            for(int y=0;y<N;y++){
                forest[x][y] = Integer.parseInt(temp.nextToken());
            }
        }

        int answer=0;

        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                answer = Math.max(answer, dp_make(x, y));
            }
        }

        System.out.println(answer);

    }

    public static int dp_make(int x,int y){
        if(cache[x][y]!=0)
            return cache[x][y];


        for (int index = 0; index < 4; index++) {
            int temp_x=x+plus[index][0];
            int temp_y=y+plus[index][1];

            if(!isRange(temp_x,temp_y) || forest[x][y] >=forest[temp_x][temp_y])
                continue;

            cache[x][y] = Math.max(cache[x][y], dp_make(temp_x, temp_y));

        }

        cache[x][y]=cache[x][y]+1;

        return cache[x][y];

    }

    public static boolean isRange(int x, int y){
        if(0>x || x>=N || 0>y || y>=N)
            return false;

        return true;
    }





}