BOJ_1937 : 욕심쟁이 판다

👉 문제링크

---

---

🔸 문제 분석 🔸

• n x n 격자판에서 상하좌우로 움직였을 때 가장 긴 이동거리를 출력한다.
• 이동 시 현재 위치 보다 큰 쪽으로만 이동할 수 있다.

🔸 문제 풀이 🔸

• 최장 이동 거리를 찾는 그래프 탐색 문제이고, 4방향 이동에 대한 정보를 따로 저장할 필요 없게 할 수 있도록 깊이 우선 탐색(DFS)를 사용한다.
• 이동은 항상 격자판의 숫자가 큰 쪽으로 이동하므로, 특정 칸으로 진입하는 방향이 달라도 나가는 최적의 방법은 항상 같다. DP를 이용한다.
  • 이 원리를 이용해서 한 격자 칸에서 시작해서 최장 몇 길이까지 이동할 수 있는지 dp 배열에 저장해간다.
  • 이미 탐색했던 칸이라면, 재탐색 할 필요 없이 기존 최장값을 이용하면 된다.
• 모든 칸에서 시작해보고 최대값을 구해 출력한다.

🔸 코드 🔸

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

public class Main {
    private static int N, max;
    private static int[][] map, dp;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = 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());
            }
        }

        // DFS
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                max = Math.max(max, dfs(i, j));
            }
        }

        // Output
        bw.write(Integer.toString(max));
        bw.flush();
    }

    private static int dfs(int row, int col) {
        if (dp[row][col] != 0) {
            return dp[row][col];
        }
        dp[row][col] = 1;

        for (int k = 0; k < 4; k++) {
            int r = row + dx[k];
            int c = col + dy[k];
            if (0 <= r && r < N && 0 <= c && c < N && map[row][col] < map[r][c]) {
                dp[row][col] = Math.max(dp[row][col], dfs(r, c) + 1);
            }
        }

        return dp[row][col];
    }
}

🔸 코드 해석 🔸

• 재귀 메서드 dfs()에서 현재 깊이를 넘겨줄 필요 없이, 다음 칸의 좌표만 있으면 된다.
  • 이미 탐색했던 칸이라면 그 dp배열의 값을 반환한다.
  • 탐색하지 않았다면, 4방 탐색으로 및 재귀 호출로 최장값을 구한다.
  • 여기서 항상 큰 값 방향으로 이동하므로, 기존 경로와 겹칠 일이 없다.
• 모든 칸에서 시작해보고, 최대값을 출력한다.

---

🔸 end 🔸

• 처음 풀이는 단순 DFS만 적용해서 시간초과가 났다. 5~6 % 까지는 맞았는데 너무 느렸었다.
• 두번째 풀이는 DP를 적용하긴 했는데, 방문체크를 하거나 dp배열을 역방향으로 저장했다.
  • dp배열에 현재 위치까지 오는데 최장으로 걸린 길이를 저장했다. 
• 마지막 풀이는 dp배열에 현재 위치에서 몇 깊이까지 들어갈 수 있는지를 저장했다. 그리고 그 값을 반환했다.
  • 기존 코드들 보다 압도적으로 빨랐는데, 항상 큰 방향으로 이동해서 경로가 겹치지 않는다는 점도 포함시켰고,
    이미 탐색한 곳의 dp값을 잘 활용해서 그런 것 같다.
  • dp배열의 저장 값을 어떻게 설정하는지에 따라서 이렇게 효율이 달라지는구나 배울 수 있었다.