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

풀이

이 문제를 처음보고는 할수있을듯 싶어 고민하였다. 조금 생각하다 내린 나의 결론은 이 문제는 DFS와 Dp를 이용해서 푸는 문제일 것이다. 그도 그럴것이 그래프 탐색과 유사하며 동일한 루트를 여러번 갈수도 있기에 시간을 줄이면 좋으므로 Dp또한 같이 적용시켜야 할것 같았다. 알고리즘의 전체적인 개요는 우선 대나무의 양이 저장되어있는 2차원 배열을 만든다. 그러고 나서 DFS를 적용할것이므로 visite2차원 배열을 만들어준다. 그리고 나서 마지막으로 DP를 2차원배열로 선언하는데 이때 나느 선언할때 값들을 1로 전부 초기화했다. 왜냐면 만약 상하좌우의 좌표의 대나무의 양이(막혀있지 않다고 가정하였을때) 현재 위치에 존재하는 대나무의 양보다 적으면 아무데도 이동할수는 없지만 그래도 적어도 현재 위치한 자리의 대나무는 먹을수있기 때문이다. 그리고 만약 현재위치에서 이동할수있는 곳들이 여러곳이 존재한다면 가 상하좌우의 DFS결과(상하좌우로 갔을때 얼마나 더 갈수있는가.)를 temp에 저장해놓고 총 4개의 DFS값들중 최대값을 현재위치의 DP에 저장하면 된다. 그렇게 어려운 코드가 아니기때문에 코드를 보면 이해가 갈것이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

    static int N;
    static int[][] map;
    static int[][] dp;
    static boolean[][] visited;
    static int[] dr_x = {-1, 0, 1, 0};
    static int[] dr_y = {0, 1, 0, -1};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");
        N = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        dp = new int[N][N];
        visited = new boolean[N][N];

        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());
                dp[i][j] = 1;
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j])
                    DFS(i,j);
            }
        }

        int max = -1;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(max < dp[i][j])
                    max = dp[i][j];
            }
        }

        System.out.println(max);
    }

    public static int DFS(int x, int y){
        int temp = 0; //주변에 갈수있는곳들의 Dp중 가장큰 곳을 저장한 변수
        if(x < 0 || x>=N || y < 0 || y>=N)
            return 0;

        if(visited[x][y])
            return dp[x][y];

        visited[x][y] = true;
        for(int i=0; i<4; i++){
            //경계선을 벗어 났을때
            if(x + dr_x[i]<0 || x + dr_x[i]>=N || y + dr_y[i]<0 ||y + dr_y[i]>=N)
                continue;
            //다음 좌표의 대나무가 현재좌표보다 많을때 == 갈수있을때
            if(map[x + dr_x[i]][y + dr_y[i]] > map[x][y]) {
                temp = Math.max(DFS(x + dr_x[i],y + dr_y[i]), temp);
//                dp[x][y] = Math.max(DFS(x + dr_x[i],y + dr_y[i]) + dp[x][y], dp[x][y]);
            }
        }
        //map[x][y]에서 탐색이 끝났을때.
        dp[x][y] += temp;
        return dp[x][y];
    }
}

뭔가 이런 류의 문제는 풀수있을것같다. 이 문제 역시 답지를 보거나 힌트를 얻지 않고 풀었다. 풀이가 보이기 시작하니 문제를 푸는 재미가 쏠쏠하다.