BOJ 1937 - 욕심쟁이 판다

문제

BOJ 1937 - 욕심쟁이 판다

N×N 크기의 대나무 숲이 있다. 각 칸에는 대나무의 양이 적혀 있다. 판다는 어느 칸에서 출발해도 되고, 현재 칸보다 대나무가 더 많은 인접 칸(상하좌우)으로만 이동할 수 있다. 판다가 이동할 수 있는 칸의 최대 수를 구한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500)

다음 N개의 줄에 각 칸의 대나무 양이 주어진다. (0 이상 1,000,000,000 이하)

출력

판다가 이동할 수 있는 칸의 최대 수를 출력한다.

예제

입력

출력

풀이

핵심 아이디어: dp[r][c]를 (r, c)에서 출발하여 판다가 이동 가능한 최대 칸 수로 정의하고, DFS + 메모이제이션으로 계산한다. 값이 증가하는 방향으로만 이동하므로 사이클이 없어 메모이제이션이 유효하다.

모든 칸 탐색: 모든 (i, j)에 대해 recur(i, j)를 호출하여 최댓값을 갱신한다.
DFS 재귀 정의:
- dp[r][c] != 0이면 이미 계산된 값이므로 반환한다.
- dp[r][c] = 1로 초기화(자기 자신 포함)
- 4방향 인접 칸 (nr, nc) 중 map[r][c] < map[nr][nc]인 경우 recur(nr, nc) + 1과 비교하여 dp[r][c]를 최대화한다.
메모이제이션: 한 번 계산된 dp[r][c]는 재사용된다. 값이 단조 증가하는 방향으로만 이동하므로 이미 방문한 칸을 재방문하는 순환 참조가 발생하지 않는다.
정답: 전체 dp 배열의 최댓값이 정답이다.

DAG(방향 비순환 그래프) 구조를 활용한 DFS + DP의 전형적인 패턴이다.

코드

package day349;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Day343BOJ1937욕심쟁이판다 {
    static int N, ans = 0;
    static int[] dr = { 0, 0, 1, -1 }, dc = { 1, -1, 0, 0 };
    static int[][] map, dp;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        dp = new int[N][N];
 
        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++) {
                ans = Math.max(ans, recur(i, j));
            }
        }
        System.out.println(ans);
        br.close();
    }
 
    private static int recur(int r, int c) {
        if (dp[r][c] == 0) {
            dp[r][c] = 1;
            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir];
                int nc = c + dc[dir];
                if (index(nr, nc))
                    continue;
                if (map[r][c] < map[nr][nc])
                    dp[r][c] = Math.max(dp[r][c], recur(nr, nc) + 1);
            }
        }
        return dp[r][c];
    }
 
    private static boolean index(int nr, int nc) {
        return nr < 0 || nc < 0 || nr >= N || nc >= N;
    }
}

복잡도

시간: O(N²) — 각 칸을 최대 한 번씩 방문 (메모이제이션)
공간: O(N²) — map[][], dp[][] 배열

문제

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500)

다음 N개의 줄에 각 칸의 대나무 양이 주어진다. (0 이상 1,000,000,000 이하)

출력

판다가 이동할 수 있는 칸의 최대 수를 출력한다.

예제

입력

출력

풀이

모든 칸 탐색: 모든 (i, j)에 대해 recur(i, j)를 호출하여 최댓값을 갱신한다.

DFS 재귀 정의:

dp[r][c] != 0이면 이미 계산된 값이므로 반환한다.
dp[r][c] = 1로 초기화(자기 자신 포함)
4방향 인접 칸 (nr, nc) 중 map[r][c] < map[nr][nc]인 경우 recur(nr, nc) + 1과 비교하여 dp[r][c]를 최대화한다.

메모이제이션: 한 번 계산된 dp[r][c]는 재사용된다. 값이 단조 증가하는 방향으로만 이동하므로 이미 방문한 칸을 재방문하는 순환 참조가 발생하지 않는다.

정답: 전체 dp 배열의 최댓값이 정답이다.

DAG(방향 비순환 그래프) 구조를 활용한 DFS + DP의 전형적인 패턴이다.

코드

package day349;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Day343BOJ1937욕심쟁이판다 {
    static int N, ans = 0;
    static int[] dr = { 0, 0, 1, -1 }, dc = { 1, -1, 0, 0 };
    static int[][] map, dp;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        dp = new int[N][N];
 
        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++) {
                ans = Math.max(ans, recur(i, j));
            }
        }
        System.out.println(ans);
        br.close();
    }
 
    private static int recur(int r, int c) {
        if (dp[r][c] == 0) {
            dp[r][c] = 1;
            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir];
                int nc = c + dc[dir];
                if (index(nr, nc))
                    continue;
                if (map[r][c] < map[nr][nc])
                    dp[r][c] = Math.max(dp[r][c], recur(nr, nc) + 1);
            }
        }
        return dp[r][c];
    }
 
    private static boolean index(int nr, int nc) {
        return nr < 0 || nc < 0 || nr >= N || nc >= N;
    }
}