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

13 Jul 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

특정 위치에서 시작하여 상하좌우로 움직일 수 있다.

현재 칸보다 숫자가 더 큰 칸으로만 갈 수 있는데 갈 수 있는 최대 칸 수를 구하는 문제.

처음에 dfs로 풀었는데 시간초과가 났다.

모든 칸을 봐야하는데 이미 기록된 칸은 더이상 볼 필요가 없었다.

메모이제이션을 하여 dp배열에 저장된 값이 있다면 그 값을 반환해주고 바로 끝내도록 했다.

---

메모리: 37148KB

시간: 516ms

언어: Java 11

코드

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

public class Main {
    static int n;
    static int[][] forest, dp;

    static int[][] vector = { { -1, 0 }, { 1, 0 }, { 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());
        forest = 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());
            }
        }

        dp = new int[n][n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(dfs(i, j), ans);
            }
        }

        System.out.println(ans);
    }

    private static int dfs(int r, int c) {
        if (dp[r][c] > 0) {
            return dp[r][c];
        }

        dp[r][c] = 1;
        for (int i = 0; i < 4; i++) {
            int nr = r + vector[i][0];
            int nc = c + vector[i][1];

            if (nr < 0 || nc < 0 || nr >= n || nc >= n) {
                continue;
            }

            if (forest[r][c] < forest[nr][nc]) {
                dp[r][c] = Math.max(dfs(nr, nc) + 1, dp[r][c]);
            }
        }

        return dp[r][c];
    }

}