[백준 Gold 3] 1937 욕심쟁이 판다 - Java

문제링크 : https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

접근 과정 : 

• DFS를 통해서, forest[i][j] 에서 판다가 출발하는 경우를 모두 조사.
• 다만 이미 한번 조사했던 칸은 dp[i][j]에 저장된 값을 사용하여 재탐색 비용을 줄임
• 즉, DFS+메모리제이션으로 문제를 접근 (배열 이름만 dp....)
• 방문체크가 필요없는 이유 : 판다는 현재칸보다 더 큰 값의 칸으로만 이동하기 때문에 다시 같은 칸을 방문하지 않는다!!

 

소스 코드 및 결과 :

package BOJ;

/* 
    욕심쟁이 판다
*/

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

public class BOJ1397 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        forest = 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++) {
                forest[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                answer = Math.max(answer, dfs(i, j));

            }
        }

        System.out.println(answer);

    }

    static int N, answer;
    static int[][] forest;
    static int[][] dp;
    static int[][] move = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    static int dfs(int i, int j) {

        if (dp[i][j] != 0) {
            return dp[i][j];
        }

        int cnt = 0;

        for (int d = 0; d < 4; d++) {
            int x = i + move[d][0];
            int y = j + move[d][1];

            if (x<0 || x>=N || y<0 || y>=N || forest[i][j] >= forest[x][y]) {
                continue;
            }

            cnt = Math.max(cnt, dfs(x, y));
        }

        return dp[i][j] = cnt+1;
    }

}

 

P.S 

DP를 사용하는 방법도 있을거 같은데...

이건 좀 더 고민을 해보아야겠다..