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

문제 파악

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

풀이

이 문제는 각 칸마다 상하좌우로 이동하면서 나무의 값이 더 큰 칸으로만 이동할 수 있으며, 이는 DFS로 탐색하였다.

각 시작점으로부터의 경로에서는 나무의 개수가 무조건 증가해야 하므로 한 번 최대 경로를 구하게 되면 추가 연산이 불필요하다.
따라서 주어진 대나무 숲과 일치하는 depth[N][N] (r,c 시작점으로부터 판다의 경로 최대값) 배열을 선언해 메모이제이션에 사용했다.

이 둘을 혼합하면 DFS 과정 중의 중복 탐색을 방지해 복잡도를 줄일 수 있게 된다.

또한 DFS 과정은 재귀를 사용했다.

• depth[r][c] == 0 일때 depth[r][c] 리턴
• 다음 위치(상/하/좌/우)의 최대 깊이 연산(혹은 참고)후 (r,c) 위치 최대 경로 갱신 및 반환

을 수행하도록 한다.

코드

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

public class Main {
    static int[][] forest;
    static int N;
    static final int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int[][] depth;

    public static void main(String[] args) throws IOException {
        init();
        int answer = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                answer = Math.max(answer, getMaxDepth(r, c));
            }
        }
        System.out.println(answer);
    }

    private static int getMaxDepth(int r, int c) {
        if (depth[r][c] != 0) return depth[r][c];
        int subDepth = 0;
        for (int[] d : direction) {
            int nR = r + d[0];
            int nC = c + d[1];
            if (!isInBound(nR, nC) || forest[r][c] >= forest[nR][nC]) continue;
            subDepth = Math.max(subDepth, getMaxDepth(nR, nC));
        }
        return depth[r][c] = 1 + subDepth;
    }

    private static boolean isInBound(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N;
    }
	
    // 입력부 & 초기화
    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        forest = new int[N][N];
        depth = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                forest[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
    }
}