[Boj_1937] 욕심쟁이 판다

📎 문제 링크

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

 

▸ 문제

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

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

 

▸ 입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

 

▸ 출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 3
• 🔔  문제 유형 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 깊이 우선 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 DFS 만으로 해결하면 시간 초과가 나기 때문에, DP와 함께 사용하여 해결할 수 있다.

DP를 이용해 이미 탐색한 경로를 저장하고, 같은 경로를 다시 방문할 때 저장된 값을 사용하면 중복 탐색을 방지할 수 있다.

 

dp[i][j]를 좌표 (i, j)에서 출발했을 때 판다가 이동할 수 있는 최대 칸 수라고 본다.

즉,  dp[i][j] = k라면, 판다가 (i, j)에서 출발했을 때, 최대 k 칸 이동할 수 있다는 뜻이다.

이를 구하기 위해, DFS를 활용하여 네 방향으로 이동하며, 이동할 수 있는 최댓값을 계산하고 dp[i][j]에 저장한다.

 

아래와 같은 대나무 숲이 있다고 가정하자.

2	3
1	4

 

판다가 (0, 0)에서 출발한다면, 판다는 2 → 3 → 4 순서로 이동할 수 있다. 따라서 최대 이동 거리는 3이며,  dp[0][0] = 3이 된다.

 

판다가 (1, 0)에서 출발한다면, 판다는 1 →  2 → 3 → 4 순서로 이동할 수 있다.

1 →  2로 이동한 후, dp[0][0] = 3이 이미 저장되어 있으므로 dp[1][0] = dp[0][0] + 1 = 4가 된다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 40580KB
시간 : 380ms

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

public class Main {
    static int n;
    static int[][] map;
    static int[][] dp;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {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 int[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());
            }
        }

        dp = new int[n][n];
        int ans = 0; // 판다가 이동할 수 있는 칸의 수의 최댓값
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dfs(i, j));
            }
        }

        System.out.println(ans);
    }

    private static int dfs(int x, int y) {
        if (dp[x][y] != 0) { // 이미 경로가 있음
            return dp[x][y];
        }

        // 판다는 최소 한 군데에서 대나무를 먹을 수 있음
        dp[x][y] = 1;

        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + x;
            int ny = dy[i] + y;

            // 범위 체크
            if (rangeCheck(nx, ny)) continue;

            // 대나무를 먹고 자리를 옮기면 
            // 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 함
            if (map[x][y] < map[nx][ny]) {
                // 상하좌우 중 가장 많이 먹을 수 있은 경로 탐색
                dp[x][y] = Math.max(dp[x][y], dfs(nx, ny)+1);
            }
        }

        return dp[x][y];
    }

    private static boolean rangeCheck(int x, int y) {
        return x < 0 || x >= n || y < 0 || y >= n;
    }
}

 

처음에는 DFS 돌리면서 다 검사하면 된다고 생각했는데, 알고리즘 분류를 보니 DP가 있어, 다른 사람의 풀이를 보고 아이디어를 얻어 해결했다. DP는 풀기도 싫고,, 너무 어렵다,,

그래도 오랜만에 재밌는 문제를 푼 것 같아 포스팅해 본다 ! 😊