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

문제 링크

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

1937번: 욕심쟁이 판다

 

문제 요약

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

 

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

 

입력

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

 

출력

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

(문장이 조금 애매한데, 정확히는 판다가 임의의 어떤 칸에서 출발했을 때, 대나무를 먹을 수 있는 칸의 수의 최댓값을 출력한다. 즉 처음 출발한 칸도 포함해야한다는 것이다)

 

접근법

현재 칸보다 큰 숫자의 칸으로만 이동 가능하기 때문에 모든 경우를 다 따져보려면 모든 칸에서 한번씩 출발을 해봐야 한다.

또 각 칸에서 상하좌우로 이동을 해봐야 하기 때문에 각 칸에서 상하좌우의 칸으로 (단 현재 칸보다 큰 숫자여야 함) dfs를 해봐야 한다.

 

이 때 n의 최댓값이 500이므로, 아무 조건 없이 DFS를 전부 해봤다간 시간초과가 날 것이 분명하다. 따라서 DP 배열을 하나 만들어서, 각 칸에서 상하좌우로 DFS를 총 4번 수행해서 얻은 최대 이동값을 dp 배열의 동일한 칸에 기록한다. 그리고 다른 DFS에서 해당 칸을 방문할 경우, 그 칸에서 DFS를 다시 수행하지 않고 기록되어 있는 값을 그대로 반환한다.

 

이렇게 하면 중복된 탐색을 없애고, 반드시 필요한 dfs만 수행하게 할 수 있다.

 

*참고: 문제의 문장이 좀 모호한데, "판다의 이동 가능 횟수"를 구하는 것이 아니라, "판다가 임의의 어떤 칸에서 출발했을 때, 대나무를 먹을 수 있는 칸의 수의 최댓값"을 구해야 한다. 즉 판다가 출발한 칸도 세어야 한다는 것이다.

 

 

시간 복잡도

DP 배열을 사용하기 떄문에 DFS로 모든 칸을 한 번씩만 탐색하면 된다.

O(N^2)

 

 

공간 복잡도

대나무숲과 DP 배열 정도의 메모리가 필요하다.

2 * N^2 * sizeof(int) bytes

 

 

풀면서 놓쳤던 점

딱히 없다.

 

 

이 문제에서 얻어갈 점

DFS와 DP.

 

 

코드

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

public class Main
{
    static int N;
    static int[][] bamboos;
    static int[][] maxMovesArr; //DP 배열
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //상하좌우 이동에 쓰일 배열

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

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

        bamboos = new int[N][N];
        readBamboos();

        System.out.println(getMaxMoves());
    }

    static int getMaxMoves()
    {
        int maxMoves = 0;

        //DP 배열 생성 및 0으로 초기화
        maxMovesArr = new int[N][N];

        for (int row = 0; row < N; row++)
        {
            for (int col = 0; col < N; col++)
                maxMoves = Math.max(maxMoves, dfs2GetMaxMoves(row, col)); //모든 칸에서 DFS
        }

        return maxMoves;
    }

    //DFS를 하며 최댓값을 구하고 기록하는 함수
    static int dfs2GetMaxMoves(int row, int col)
    {
        //이미 DP 배열에 값이 있으면 바로 return
        if (maxMovesArr[row][col] != 0)
            return maxMovesArr[row][col];

        //출발하는 칸을 포함해야 하기 때문에 1부터 시작
        int maxMoves = 1;

        //상하좌우로 움직이며 DFS가 가능할 경우 DFS
        int nextRow, nextCol;
        for (int[] dir : dirs)
        {
            nextRow = row + dir[0];
            nextCol = col + dir[1];

            if (!isInMap(nextRow, nextCol))
                continue;

            if (bamboos[nextRow][nextCol] <= bamboos[row][col])
                continue;

            //해당 칸으로 한 칸 움직였으므로 + 1 한 값과 비교해야함
            maxMoves = Math.max(maxMoves, dfs2GetMaxMoves(nextRow, nextCol) + 1);
        }

        //DP 배열에 기록
        maxMovesArr[row][col] = maxMoves;

        return maxMoves;
    }

    //해당 row, col이 범위 내의 값인지 확인
    static boolean isInMap(int row, int col)
    {
        return row >= 0 && row < N && col >= 0 && col < N;
    }

    static void readN() throws IOException
    {
        N = Integer.parseInt(br.readLine());
    }

    static void readBamboos() throws IOException
    {
        StringTokenizer st;

        for (int row = 0; row < N; row++)
        {
            st = new StringTokenizer(br.readLine());
            for (int col = 0; col < N; col++)
                bamboos[row][col] = Integer.parseInt(st.nextToken());
        }
    }
}