[BOJ - JAVA] 1937 - 욕심쟁이 판다 (DFS)

# 주소

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

1937번: 욕심쟁이 판다

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    static int n,m;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] arr;
    static int[][] dp;
    static int max = 0;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = scan.nextInt();
            }
        }
        dp = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                max = Math.max(dfs(i,j), max);
            }
        }
        System.out.println(max);
    }
    public static int dfs(int x, int y) {
        if (dp[x][y] != 0) {
            return dp[x][y];
        }
        dp[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                if(arr[nx][ny] > arr[x][y])
                    dp[x][y] = Math.max(dp[x][y], dfs(nx,ny) + 1);
            }
        }
        return dp[x][y];
    }
}

풀다가 DP도 들어가는걸 보고 음 메모제이션이 들어가는게 합리적이란 생각을 했습니다.

기본적으로 n의 값이 100만까지 들어갈 수 있기 때문에 이 모든 100만x 100만의 배열을 dfs로 구하면 컴퓨터가 터질 것입니다.

그러므로 메모이제이션으로 반드시 풀어야 하는데요.

메모이제이션은, 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법입니다. 동적 계획법의 핵심이 되는 기술로써 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식입니다.

따라서 dfs문을 계속 실행하면서 방문한 dp에 대해서는 굳이 dfs문을 돌릴 이유가 없기 때문에 메모이제이션이 도입됩니다.

무슨말인고 하면

1	2	4
3	5	11
6	7	9

이라고 해봅시다.

그럼 1 2 5 7 9를 선택하는 것이 제일 크므로 정답은 5입니다.

그렇기 때문에 dp[0][0] = 5이고 dp[0][1] = 4가 되겠지요.

이미 dp[0][0]을 구함으로써 dfs가 동장해, dp가 지나간 공간에 이미 다 값을 채워넣게됩니다.

그런데 굳이 dp[0][1]을 방문할 필요가 있을까요? 어자피 dp[0][0]이 더 큰데 말이죠.

그래서 과감하게 dp의 값이 0이 아닌 곳은 return해버리는 것입니다.

이렇게 함으로써 모든 dfs지점을 방문할 수 있고 또 전부다 dfs로 돌리는 것 보다 방문한 값은 과감하게 버리는 방식을 채택함으로써 빠른 계산속도를 보여줄 수 있습니다.

감사합니다.