[백준] 1937번 : 욕심쟁이 판다 (Java)

🔗 1937번 : 욕심쟁이 판다
● Java 풀이
● 시간 제한 2초
● 메모리 제한 256 MB

문제

 

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

 

풀이

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

public class Main {
    private static int N;  // 숲 크기 (최대 500)
    private static long MAX_MOVE;
    private static long[][] map, dp; // 숲, 최대 먹을 수 있는 양 DP
    private static final int[] dr = {-1, 1, 0, 0}, dc = {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());
        map = new long[N][N];
        dp = new long[N][N];

        StringTokenizer st;
        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());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (dp[i][j] == 0) {  // 해당 칸에 방문한 적이 없을 경우
                    MAX_MOVE = Math.max(MAX_MOVE, findMaxMove(i, j));  // 현재 칸의 이동 가능 값과 최대 이동 가능 값 비교
                }
            }
        }

        System.out.println(MAX_MOVE);
    }

    private static long findMaxMove(int r, int c) {
        if (1 <= dp[r][c]) return dp[r][c];  // 방문한 적이 있을 경우 해당 칸부터 갈 수 있는 최대 거리 반환
        dp[r][c]++;  // 방문한 적이 없을 경우 방문 처리 (+ 1)
        int nr, nc;
        for (int i = 0; i < 4; i++) {  // 사방 탐색
            nr = r + dr[i];
            nc = c + dc[i];

            if (canMove(nr) && canMove(nc) && map[r][c] < map[nr][nc]) {  // 이동할 수 있을 경우 (더 많은 대나무 존재)
                dp[r][c] = Math.max(1 + findMaxMove(nr, nc), dp[r][c]);  // 해당 방향으로 이동할 때의 최대 값이 다른 방향으로 이동했을 때의 최대값보다 큰지 비교
            }
        }

        return dp[r][c];  // 구한 값 반환
    }

    private static boolean canMove(int n) {  // ArrayOutOfIndex 방지
        return (0 <= n && n < N);
    }
}

 

시간 제한도, n의 MAX 크기도, 메모리도 괜찮아서 그냥 완탐으로 풀어도 되지 않을까? 라는 생각은 했지만

떠먹여주는 DP길래 DP로 풀어버렸다.

판다 문제는 골드 3을 주로 푸는 사람들이 푼다면 되려 쉽게 느낄 수도 있을 것 같다.

 

골드3부터는 거의 DP 문제로, 어떤 데이터를 저장하고, 그 데이터를 얼마나 잘 활용하냐의 싸움인 것 같다.

그리고 또 중요한 것은 문제 이해 능력...

조그만한 거 하나라도 놓치면 안 풀린다든지, 문제 접근을 설명과 반대로 해야한다든지 하는 경우가 많은 것 같다.

 

boolean으로 방문 체크를 굳이 해주지 않는 이유는,

한 재귀 사이클에서 중복 경로를 탐색할 수가 없다 (작은 요소에서 큰 요소로 가기 때문)

다른 방문 위치는 DP 2차원 배열 내에 값 존재 여부로 판단하면 된다. (방문 위치는 1부터 시작하기 때문)

개인적으로 DP 2차원 배열을 -1이나 INF 값으로 초기화해줄 필요가 없어서 좋았다 ㅎㅎ