[백준] 1937번 : 욕심쟁이 판다 - 자바(JAVA)

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

1937번: 욕심쟁이 판다

 

문제 해석

n x n의 크기 대나무 숲이 존재합니다.

욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작합니다.

그리고 그곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동합니다.

그리고 그곳에서 또 대나무를 먹습니다.

 

대나무를 먹는 조건

1. 옮긴 지역에는 전 지역보다 대나무가 많아야 한다.

 

판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하라.

 

문제 풀이 전 설계

어떤 지점에 판다를 처음 풀어놓아야 하는지 정해져 있지 않습니다.

가장 심플한 생각으로는 각 칸마다 검사를 진행하면서 자신보다 큰 수로 DFS를 합니다.

 

여기서 시간복잡도를 줄일 수 있는 방법으로는 이미 탐색한 경로의 경우에는 재탐색하지 않는 방법을 선택합니다.

DP [][] 배열을 선언하여 이미 방문한 경우에는 1 + 방문한 정점의 경우의 수를 반환하고 다음 칸을 검사합니다.

 

 

문제 풀이 하면서

BFS로 그냥 탐색하게 되면 문제가 발생합니다.

1 2 3 4

8 7 6 5

9 10 11 12

16 15 14 13

 

만약 1 -> 2 -> 3 -> 4 순차적으로 탐색하게 되면 16이 가능하지만

1 -> 8 -> 9 이런 식으로 탐색해 버린다면 훨씬 작은 값이 출력됩니다.

따라서 PQ를 도입해서 작은 값부터 탐색할 수 있도록 해야 할 것 같습니다.

 

하지만 BFS + PQ로 정답은 잘 나왔지만 메모리 초과, 시간 초과의 늪을 빠져나올 수 없었습니다.

 

위의 DP + DFS 풀이가 맞았는데 BFS로도 되지 않을까라는 생각에 다른 길로 빠졌었습니다.

 

코드

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

public class Main_1937_욕심쟁이판다 {
    static int n, result;
    static int[][] board, DP;

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

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

        board = new int[n][n];
        DP = new int[n][n];

        StringTokenizer st = null;
        for (int y = 0; y < n; y++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int x = 0; x < n; x++) {
                board[y][x] = Integer.parseInt(st.nextToken());
            }
        }
        //입력끝

        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) {
                result = Math.max(result , search(y, x));
            }
        }

        System.out.println(result);
    }

    private static int search(int y, int x) {
        //이미 방문된 경우
        if(DP[y][x] !=0 ){
            return DP[y][x];
        }

        //방문체크용
        DP[y][x] = 1;

        for(int k=0; k<4; k++){
            int ny = y + dy[k];
            int nx = x + dx[k];
            if(!isValid(ny,nx)){
                continue;
            }
            if(!isNextBig(board[y][x], board[ny][nx])){
                continue;
            }
            DP[y][x] = Math.max(DP[y][x], search(ny,nx) +1);

        }
        return DP[y][x];
    }

    private static boolean isValid(int tempY, int tempX) {
        return tempY >= 0 && tempX >= 0 && tempY < n && tempX < n ;
    }

    private static boolean isNextBig(int curValue, int nextValue) {
        return curValue < nextValue;
    }
}

 

출처

https://steady-coding.tistory.com/39