[백준] 1937번 '욕심쟁이 판다' - Java

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

1937번: 욕심쟁이 판다

---

문제

---

코드

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int[][] node;
	private static int[][] dp;
	private static int n;
	
	private static int[] rangeX = {-1, 1, 0, 0};
	private static int[] rangeY = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(bf.readLine());
		node = new int[n][n];
		dp = new int[n][n];
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());			
			for(int j = 0 ; j < n ; j++) {
				node[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int ans = 0;
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				ans = Math.max(ans, dfs(i, j));
			}
		}
		
		bw.write(Integer.toString(ans));
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	public static int dfs(int x, int y) {
		if(dp[x][y] != 0) {
			return dp[x][y];
		}
		
		dp[x][y] = 1;
		
		int dx, dy;
		for(int i = 0 ; i < 4 ; i++) {
			dx = x + rangeX[i];
			dy = y + rangeY[i];
			
			if(dx < 0 || dy < 0 || dx > n-1 || dy > n-1) {
				continue;
			}
			
			if(node[x][y] < node[dx][dy]) {
				dp[x][y] = Math.max(dp[x][y], dfs(dx, dy) + 1);
				dfs(dx, dy);
			}
		}
		return dp[x][y];
	}
}

다이나믹 프로그래밍과 그래프탐색이 섞인 문제였습니다. 저번 알고스팟이랑 비슷한 것 같은데 이게 더 쉽네요..