[BaekJoon] 1937 욕심쟁이 판다 (Java)

1.  문제 링크

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

2.  문제

요약

• n x n의 크기의 대나무 숲이 있는데 판다는 어떤 지역에서 대나무를 먹기 시작합니다.
• 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 하고 또 그곳에서 대나무를 먹습니다.
• 그러나 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 합니다.
• 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통해 움직여야 하는지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 500보다 작거나 같은 대나무 숲의 크기 n이 주어지고 두 번째 줄부터 n개의 줄에는 대나무 숲의 정보가 주어집니다. 대나무 숲의 정보는 1,000,000보다 작거나 같은 자연수인 각 지역의 대나무의 양이 주어집니다.
• 출력: 첫 번째 줄에 판다가 이동할 수 있는 칸의 수의 최댓값을 출력합니다.

3.  소스코드

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

public class Main {
	static int n, max = Integer.MIN_VALUE, temp = Integer.MIN_VALUE;
	static int[][] map, dp;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	static void input() {
		Reader scanner = new Reader();
		n = scanner.nextInt();
		map = new int[n][n];
		dp = new int[n][n];
		for(int row = 0; row < n; row++) {
			for(int col = 0; col < n; col++)
				map[row][col] = scanner.nextInt();
		}
	}
	
	static void solution() {
		for(int row = 0; row < n; row++) {
			for(int col = 0; col < n; col++) {
				max = Math.max(max, dfs(row, col));
			}
		}
		System.out.println(max);
	}
	
	static int dfs(int x, int y) {
		if(dp[x][y] != 0) {
			return dp[x][y];
		}
		dp[x][y] = 1;
		for(int direction = 0; direction < 4; direction++) {
			int cx = x + dx[direction];
			int cy = y + dy[direction];
			if(cx >= 0 && cx < n && cy >= 0 && cy < n) {
				if(map[cx][cy] > map[x][y]) {
					dp[x][y] = Math.max(dp[x][y], dfs(cx, cy) + 1);
				}
			}
		}
		return dp[x][y];
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}