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

 

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

문제분석

판다가 갈 수 있는 '가장 긴 거리' 를 알아내는 문제이다. 핵심은 dp를 "얼마나 더 갈 수 있는지 저장" 하는 것이다. 문제를 보면 알겠지만, 모든 칸에서 DFS를 돌아야 한다. 따라서, 가지치기를 통해 DFS횟수를 최소화 하는 것이 가장 중요하다.

처음에는 깊이(depth)를 파악하려고 했다. 하지만 이렇게 된다면 DFS를 최소화하지 못하고, 시간초과로 틀리게 된다.

따라서, DFS를 할 때 dp에 값이 없으면, 모든 방향 DFS를 돌고 그중 최고값을 저장하게 끔 해야한다.

쉽게말해, "애매하게 여러 번 보다, 확실하게 한번" 계산하자는 게 이 문제의 목적이다.

 

코드

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

public class Main {
    static int[][] map;
    static int[][] dp;
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, -1, 0, 1 };
    static int max = Integer.MIN_VALUE;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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++) {
                int input = Integer.parseInt(st.nextToken());
                map[i][j] = input;
                dp[i][j] = 0;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = DFS(i, j);
            }
        }
        System.out.println(max);
    }

    static int DFS(int r, int c) {
        if (dp[r][c] != 0) { // dp값이 저장된 게 있는 경우 해당 값 반환.
            return dp[r][c];
        } else {
            int t = 0;

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if (nr >= 0 && nc >= 0 && nr < n && nc < n && map[r][c] > map[nr][nc]) {
                    t = Math.max(t, DFS(nr, nc));
                }
            }
            dp[r][c] = t + 1;
            max = Math.max(dp[r][c], max);
            return dp[r][c];
        }

    }
}