[백준] 1937번. 욕심쟁이 판다(JAVA)

문제

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

---

풀이(20분)

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int[][] dp;
    static int[][] map;
    static int[] dx = new int[]{0, 0, -1, 1};
    static int[] dy = new int[]{-1, 1, 0, 0};

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

        n = Integer.parseInt(br.readLine());
        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++){
                if(dp[i][j] == 0){
                    dp(i, j);
                }
            }
        }

        int max = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                max = Math.max(max, dp[i][j] + 1); // 자기 자신 포함이기때문에 +1
            }
        }

        System.out.println(max);
    }

    static int dp(int row, int col){
        if(dp[row][col] != 0){ // 이미 탐색된 경우 값 반환
            return dp[row][col];
        }

        for(int i = 0; i < 4; i++){
            int nextRow = row + dx[i];
            int nextCol = col + dy[i];
            if(!isInBounds(nextRow, nextCol)){ // 범위 밖이라면 패스
                continue;
            }
            if(map[row][col] >= map[nextRow][nextCol]){ // 갈 수 없는 경로라면 패스
                continue;
            }
            dp[row][col] = Math.max(dp[row][col], dp(nextRow, nextCol) + 1); // 다음 경로와 비교
        }

        return dp[row][col];
    }

    static boolean isInBounds(int row, int col){
        return row >= 0 && row < n && col >= 0 && col < n;
    }

}

---

문제 풀이 전략

 

n = 500이기 때문에 단순 dfs를 활용하면 시간복잡도에서 오류가 발생할 수 있다.

따라서 dp배열을 활용하여 이미 탐색이 완료된 경우라면 더 이상 탐색하지 않게 했다.

 

어떻게 보면 백트래킹일 수도 있고 dp일 수도 있는 문제 같다.