(JAVA) [BOJ]백준 1937번, 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

 

 

1937, 욕심쟁이 판다

📌 난이도 : Gold 3

📌 알고리즘 : DFS, DP

 

이번 문제는 모든 구간에 대해 무지성으로 DFS를 돌렸다가 가차없이 시간초과가 나와서 DFS + DP로 해결한 문제이다.

 

🧩 프로세스

📚 초기화 및 선언

: 숲의 크기 N을 기반으로 숲의 정보들을 입력한다.

 

📚 탐색

: 이동할 수 있는 칸의 수를 저장할 DP를 기반으로 탐색을 진행하며 최대값을 갱신해준다.

여기서 주의할 점은 이동할 칸의 수가 더 작거나 같은 경우의 예외처리를 진행해 주어야 한다.

한칸씩 움직일 수 있기 때문에 결론적으로 dp[y][x] 는 dp[y][x] 와 DFS(nx,ny) + 1 중 최대값으로 갱신해주면 된다.

( DFS(nx,ny) + 1 = 상하좌우 중에서 가장 오랫동안 생존할 수 있는 기간 +1 )

public static void main(String[] args) throws IOException {    
    N = Integer.parseInt(br.readLine());
    map = new int[N][N];
    dp = new int[N][N];

    StringTokenizer st;
    for(int i=0; i<N; i++) {
        st = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    MAX = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            MAX = Math.max(DFS(j, i), MAX);
        }
    }

    System.out.println(MAX);
}

public static int DFS(int x, int y) {
    if(dp[y][x] != 0) {
        return dp[y][x];
    }

    dp[y][x] = 1;

    for(int k=0; k<4; k++) {
        int nx = x + dir[k][0];
        int ny = y + dir[k][1];

        if(nx<0||ny<0||nx>=N||ny>=N) continue;
        if(map[y][x] >= map[ny][nx]) continue;

        dp[y][x] = Math.max(dp[y][x], DFS(nx, ny)+1);
    }

    return dp[y][x];
}

✅ 전체 코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] map, dp, dir = {{1,0},{-1,0},{0,1},{0,-1}};
    static int N, MAX;

    public static void main(String[] args) throws IOException {    
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[N][N];

        StringTokenizer st;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        MAX = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                MAX = Math.max(DFS(j, i), MAX);
            }
        }

        System.out.println(MAX);
    }

    public static int DFS(int x, int y) {
        if(dp[y][x] != 0) {
            return dp[y][x];
        }

        dp[y][x] = 1;
        
        for(int k=0; k<4; k++) {
            int nx = x + dir[k][0];
            int ny = y + dir[k][1];

            if(nx<0||ny<0||nx>=N||ny>=N) continue;
            if(map[y][x] >= map[ny][nx]) continue;

            dp[y][x] = Math.max(dp[y][x], DFS(nx, ny)+1);
        }

        return dp[y][x];
    }
}