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

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

예제 입력 1

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력 1

4

 

소스코드

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

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, result=Integer.MIN_VALUE;
	private static int [][]map;
	private static int [][]dp;
	private static int []dx= {-1,1,0,0};
	private static int []dy= {0,0,-1,1};
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		map=new int[N][N];
		dp=new int[N][N];	// startR, startE, endR, endE
			for(int r=0;r<N;r++) {
				for(int c=0;c<N;c++) dp[r][c]=-1;
			}
		
		for(int r=0;r<N;r++) {
			st=new StringTokenizer(br.readLine());
			for(int c=0;c<N;c++) {
				map[r][c]=Integer.parseInt(st.nextToken());
			}
		}
		
		for(int r=0;r<N;r++) {	// 모든 좌표를 돌며 dp값을 업데이트 함
			for(int c=0;c<N;c++) {
				int cnt=dfs(r, c);
				result=Math.max(result, cnt);
			}
		}
		
		System.out.println(result);
	}

	private static int dfs(int r, int c) {
		if(dp[r][c]!=-1) return dp[r][c];	// 이미 방문했던 곳이면 해당 값을 리턴
		
		dp[r][c]=1;	// 아직 방문하지 않은 곳이면 현재 위치에서 이미 1번 방문한 것이므로 1을 저장함
		for(int d=0;d<4;d++) {	// 사방탐색
			int nx=r+dx[d];
			int ny=c+dy[d];
			
			if(isIn(nx, ny) && map[nx][ny]>map[r][c]) {	// 이동 가능한 영역일 경우
				dp[r][c]=Math.max(dp[r][c], dfs(nx, ny)+1);	// 현재 저장된 dp값과 새로운 경로로 이동했을 경우 중 더 큰 값을 저장
			}
		}
		
		return dp[r][c];
	}
	
	
	private static boolean isIn(int r, int c) {
		return r>=0 && r<N && c>=0 && c<N;
	}
}

https://sujin7837.tistory.com/411

[Java] 백준 1520번 : 내리막 길

위 문제와 유사하게 dfs+dp를 이용하는 문제였습니다.

다만, 시작점과 끝점을 모르기 때문에 모든 좌표를 시작점으로 dp값을 업데이트 해주어야 한다는 점에서 좀 더 난이도가 있었습니다.