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

1. 문제

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

2. 접근법

DFS/BFS

• 시간복잡도가 N^2의 칸에 대하여, N^2의 연산을 수행하니 O(N^4)가 된다.

• N의 최댓값이 500이니, 500^4 = 625억으로 시간초과가 난다!

DFS + DP

• Memorization으로 판다가 방문한 칸의 최대를 기록하자!

• 만약 아래와 같은 필드가 있다고 가정하자.
  

• 아래와 같이 DP 배열을 갱신하자.

1. 먼저 (1, 1) 의 DP 값이 -1이니 재귀를 이용해 상, 하, 좌, 우로 이동할 수 없는 칸이 나올때까지 검색한다. (기존 칸보다 이동할 칸의 대나무가 더 많아야 한다.)

2. 만약 (2, 1)같이 이동할 수 없는 칸을 만났다면, DP 배열의 값을 1로 갱신하자. (2, 1)에서는 1칸이 최대 방문횟수로 확정하고, 나중에 (2, 1)을 만났을 때 이 값을 활용하자.

3. 예를 들어 (2, 2)에 왔을 때, (2, 1)에 이동해 다시 검색할 수 있지만, (2, 1)에서 최대로 방문할 수 있는 칸인 DP[2][1]이 1칸 이므로 DP[2][2]에는 (현재 (2, 2) 칸 + DP[2][1])인 2를 갱신한다.

4. 이런 방식으로 모든 DP 배열을 갱신한 후, 최댓값을 산출하자. 최댓값 4가 정답이다.

• 위 알고리즘같이 탐색하면, 최종 시간복잡도는 O(N^2)이 된다!
  
  
  

3. 구현하기

• DFS + DP 방식을 Java 코드로 구현해봤다.

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

public class p1937 {
    static int N;
    static int[][] field, dp;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static int dfs(int y, int x) {
        if (dp[y][x] > -1) {
            return dp[y][x];
        }

        int ret = 0;

        for (int d = 0; d < 4; d ++) {
            int ny = y + dy[d], nx = x + dx[d];
            int eat = 1;

            if (0 <= ny && ny < N && 0 <= nx && nx < N) {
                if (field[ny][nx] > field[y][x]) {
                    eat += dfs(ny, nx);
                }
            }

            ret = Math.max(ret, eat);
        }

        dp[y][x] = ret;
        return ret;
    }

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

        field = new int[N][N];
        dp = new int[N][N];

        for (int y = 0; y < N; y ++) {
            for (int x = 0; x < N; x ++) {
                dp[y][x] = -1;
            }
        }

        for (int y = 0; y < N; y ++) {
             st = new StringTokenizer(br.readLine());
             for (int x = 0; x < N; x ++) {
                 field[y][x] = Integer.parseInt(st.nextToken());
             }
        }

        for (int y = 0; y < N; y ++) {
            for (int x = 0; x < N; x ++) {
                dfs(y, x);
            }
        }

        int answer = 0;
        for (int[] line : dp) {
            for (int elm : line) {
                answer = Math.max(answer, elm);
            }
        }
        System.out.println(answer);
    }
}

4. 여담

• 역시 DP 문제는 많이 풀어봐야 한다고 느꼈습니다. 이전에 비슷한 유형을 푼적 있어서, 바로 해결했네요.