[백준] 욕심쟁이 판다 - Java

문제 출처

https://www.acmicpc.net/problem/1937

문제

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

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

입력

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

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

예제 입력 1

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력 1 

4

풀이 방법

• dfs와 dp를 이용하여 풀이하였다

전체적인 풀이 과정은 다음과 같다
- dfs만 이용하게되면, 전체 탐색을 한다. 이 때 범위가 500 x 500 이므로 최대 250,000 크기의 2차원 배열을 완전탐색하게되면 반드시 시간초과가 날것... 따라서 dp를 활용하여 가지치기를 해준다!

 

• 배열이 해당 처럼 생성이 되어있다면, 최대 칸수는 1 -> 2 -> 5 -> 7 -> 8 -> 9 ... ((1,2) 위치의 2로 시작해도 6칸이긴하다.) 총 6칸이 최대가 된다. 
• 이 때, 1 다음으로 마주치는 7 -> 8 -> 9 에 대해서는 6칸 보다 크지 않음이 자명하기 때문에 굳이 탐색을 할 필요가 없다.
  • 탐색을 0,0 부터 순차적으로 가정하기 때문에, 2, 5는 탐색이 어쩔 수 없이 진행된다.
• 따라서 dfs로 해당 칸 부터 시작하여 움직일 수 있는 최대 칸을 dp배열에 모두 삽입 시켜놓고, 0이 아닌 값으로 만들어버려 다음 탐색때 접근조차 하지 못하도록 막는다.

풀이 코드

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

public class Main {
    static int n;
    static int[][] dp;
    static int[][] map;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());

        dp = new int[n][n];
        map = 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 max = 0;
        for(int i = 0 ; i < n; i++){
            for(int j = 0; j < n; j++){
                max = Math.max(dfs(i, j), max);
            }   
        }

        System.out.println(max);
    }
    
    public static int dfs(int r, int c){
        if(dp[r][c] != 0){
            return dp[r][c];
        }

        //방문 처리와 자기지역은 입장한 것이므로
        dp[r][c] = 1;

        for(int d = 0; d < 4; d++){
            int nr = r + dr[d];
            int nc = c + dc[d];

            if(nr >= 0 && nr < n && nc >= 0 && nc < n){
                //더 큰 곳으로 가야함
                if(map[nr][nc] > map[r][c]){
                    dp[r][c] = Math.max(dp[r][c], dfs(nr, nc) + 1);
                }
            }
        }
        return dp[r][c];
    }
}

결과

회고

• 어렵다 어려워