문제

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

접근

시작점이 안 정해져 있는데 n이 500으로 크지 않고 시간 제한도 그래도 2초로 넉넉한 편이라 모든 칸에 대해 대해 각각을 시작점으로 해서 최대 이동 횟수를 구한 다음에 그중 최댓값을 찾아도 되겠다고 생각했다.
물론 무작정 탐색을 하면 당연히 안 되고... 이차원 배열에 현재 위치에서 시작해 이동할 수 있는 최대 칸 수를 메모이제이션해두어 불필요한 중복 탐색을 줄여야 한다.
어떤 칸에서부터 시작해서 이동할 수 있는 최대 칸 수는 max(상하좌우에 인접해 있는 칸에서부터 시작해서 이동할 수 있는 최대 칸 수 + 1)이다. 물론 상하좌우에 인접해 있더라도 현재 위치한 칸보다 작은 숫자로는 이동할 수 없다고 했으니 그 경우는 고려할 필요 없고.
어떤 칸을 시작점으로 했을 때의 최댓값을 이전에 이미 구한 적 있다면 그대로 쓰고, 구한 적 없다면 dfs로 더 이상 이동할 수 없을 때까지 (상하좌우에 현재 자신의 위치보다 큰 칸이 없을 때까지) 탐색해서 구하면 된다.

구현

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

class Main {
    static int n;
    static int[][] arr;
    static int[][] dp;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n][n];
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                answer = Math.max(answer, dynamicProgramming(i, j));
            }
        }
        
        System.out.println(answer);
    }

    private static int dynamicProgramming(int row, int col) {
        if (dp[row][col] == 0) {
            dp[row][col] = 1;
            for (int i = 0; i < 4; i++) {
                int nextRow = row + dx[i];
                int nextCol = col + dy[i];
                if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n && arr[nextRow][nextCol] > arr[row][col]) {
                    dp[row][col] = Math.max(dp[row][col], 1 + dynamicProgramming(nextRow, nextCol));
                }
            }
        }

        return dp[row][col];
    }
}

dp와 dfs가 결합되어 있긴 한데 풀이 방향은 명확해서 어렵지 않게 풀었다.