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

[Gold III] 욕심쟁이 판다 - 1937

문제 링크

성능 요약

메모리: 41028 KB, 시간: 404 ms

분류

깊이 우선 탐색(dfs), 다이나믹 프로그래밍(dp), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

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

입력

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

출력

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

---

풀이

각각의 좌표에 대해 dfs를 하면 쉽게 구할 수 있지만, 시간 초과가 날 것 같았다.

해당 좌표보다 큰 좌표로만 이동할 수 있기 때문에, 한 번 방문한 좌표에 대해서는 이동 가능한 경로의 수를 dp 배열에 저장하였다.

사방탐색을 하며 자신보다 큰 좌표에서 움직일 수 있는 경로에 1을 더한 값을 비교한다. 그 중 최대값이 자신의 dp값(이동 가능한 경로의 수)가 된다.

package BOJ.Gold.g3;

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

public class BOJ_1937_욕심쟁이판다 {

    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};
    static int N;
    static int[][] map;
    static int ans;
    static boolean[][] visited;

    static int[][] dp;

    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];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        dp = new int[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
                if (!visited[i][j])
                    ans = Math.max(ans, dfs(i, j));
            }

        System.out.println(ans + 1);
    }

    static int dfs(int i, int j) {
        if (visited[i][j]) return dp[i][j];

        visited[i][j] = true;
        for (int d = 0; d < 4; d++) {
            int nr = i + dr[d];
            int nc = j + dc[d];
            if (nr >= 0 && nr < N && nc >= 0 && nc < N && map[nr][nc] > map[i][j])
                dp[i][j] = Math.max(dp[i][j], dfs(nr, nc) + 1);
        }

        return dp[i][j];
    }
}