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

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

1937번: 욕심쟁이 판다

풀이 방법

dp로 풀어야 하는 문제이다. dp를 설정할 때 문제를 잘 나누어야 한다. 

dp를 나눌 때 이전 상황에 영향을 받지 않고 앞으로의 상황에만 영향을 받도록 문제를 나누었다.

dp[y][x]를 y, x에서 최대로 이동할 수 있는지로 설정했다. 

dfs함수 안에서 이동 가능한 부분으로 이동할 때 ret의 값과 1 + dfs(ny, nx) 값 중 더 큰 값을 ret에 업데이트해주므로

상, 하, 좌, 우 중 가장 큰 값을 구했다.

 

import java.io.*;
import java.util.*;
public class Main {

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int N;
    static int[][] board;
    static int[][] dp;

    public static int dfs(int y, int x) {
        if (dp[y][x] != -1) return dp[y][x]; // dp 값 활용
        int ret = 1;
        for (int i = 0;i < 4;i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny >= 0 && nx >= 0 && ny < N && nx < N){
                if (board[ny][nx] > board[y][x]) {
                    ret = Math.max(ret, 1 + dfs(ny, nx)); // ny, nx로 이동 가능하므로 + 1을 해주었다. 
                }
            }
        }
        dp[y][x] = ret;
        return dp[y][x];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        board = new int[N][N];
        dp = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        int ans = 0;
        for (int i = 0;i < N;i++) {
            for (int j = 0;j < N;j++) {
                ans = Math.max(ans, dfs(i, j));
            }
        }
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}