[백준] 1937 욕심쟁이 판다 - DP + 깊이우선탐색(DFS) JAVA

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

1937번: 욕심쟁이 판다

코드설명

깊이우선탐색 DFS와 DP를 활용하는 문제입니다.

 

DP[R][C] 에서 의미하는 바는 (R, C)에서 최대한 많은 칸을 이동할 수 있는지를 의미합니다.

만약, DFS를 통하여 (0,0) ~ (N, N)까지 모든 경우를 다 깊이우선탐색으로 조사할경우 시간초과가 납니다.

DP를 통하여 해당 위치가 이미 조사된 적이 있다면, 해당 칸에서 이미 최대한 많이 칸을 이동하는 경우를 저장해놓으므로 그 값을 가져오며 진행하면 됩니다.

 

코드

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

public class Main {
	
	public static int T, N, M;
	public static int[][] arr;
	public static int[][] dp;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1}; 
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = 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++) {
    			arr[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) {
    				answer = Math.max(answer, simulate(i, j));
    			}
    		}
    	}
    	System.out.println(answer + 1);
	}
	
	public static int simulate(int startX, int startY) {
		if(dp[startX][startY] > 0) return dp[startX][startY];
		
		for(int dir=0;dir<4;dir++) {
			int nr = startX + dx[dir];
			int nc = startY + dy[dir];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			if(arr[startX][startY] < arr[nr][nc]) { //만약 현재 위치보다 더 크다면, 깊이우선탐색
				dp[startX][startY] = Math.max(dp[startX][startY], simulate(nr, nc) + 1);
			}
		}
		
		return dp[startX][startY];
	}
}

class Node{
	int r;
	int c;
	int cnt;
	public Node(int r, int c, int cnt) {
		this.r=r;
		this.c=c;
		this.cnt=cnt;
	}
}