BOJ) 욕심쟁이 판다(1937, JAVA)

욕심쟁이 판다

1937번: 욕심쟁이 판다

풀이

 

메모이제이션을 활용한 dp문제다.

생각보다 너무 어려웠다.

알고리즘을 조금 쉬었다가 메모이제이션을 적용시켜서 dp를 활용하려니까 감이 잡히지 않았다.

그래서 다른 사람들의 풀이를 보면서 이해했다.

 

먼저, out of index를 방지해줄 inInArea 메소드와 움직일 수 있는 조건인지 확인하는 canMove 메소드를 만들었다.

이후, dfs 메소드인 findBamboo를 통해 문제의 조건에 따라 움직이며 최대 날을 구했다.

해당 위치에서 dp가 0이 아니라면 그대로 return해준다. (근처에서 가장 낮은 나무가 아니라는 소리다.)

 

dp가 0인 경우 (방문한 적 없는 구역 or 시작)이면 dp를 1로 설정해주고, 4방향으로 인접한 곳의 findBamboo 결과값 +1과 현재 위치의 dp값으로 최대값을 갱신한다.

코드를 이해하기에는 어렵지 않았지만, 생각해내는 과정이 어려운 문제인 것 같다.

 

코드

 

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

public class Main {
    static int size;
    static int[][] map, dp;

    final static int[] dx= {1,-1,0,0}, dy= {0,0,1,-1};

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

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

    private static void solution() {
        int answer =0;
        for(int y=0; y<size; y++) {
            for(int x=0; x<size; x++) {
                answer = Math.max(answer,findBamboo(x,y));
            }
        }
        System.out.println(answer);
    }

    private static int findBamboo(int x, int y) {
        if(dp[y][x] !=0)    return dp[y][x];
        dp[y][x] =1;

        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isInArea(nx,ny) && canMove(x,y,nx,ny)) {
                dp[y][x] = Math.max(dp[y][x], findBamboo(nx,ny)+1);
            }
        }

        return dp[y][x];
    }

    private static boolean isInArea(int x, int y) {
        return x>=0 && x<size && y>=0 && y<size;
    }

    private static boolean canMove(int x, int y, int nx, int ny) {
        return map[y][x] < map[ny][nx];
    }
}