[백준 1937번][Java] 욕심쟁이 판다 - DP에서 메모이제이션 가능한 상황

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

이때까지 DP와는 성격이 조금 다른 문제였다.

이전까지는 단순히 완전 탐색의 바텀업 버전이었지만 이 문제는 재귀를 이용한 탑다운 방식에 cache배열을 추가하면서 해결할 수 있다.

 

이 문제에서 가장 중요한 한 문장이 있다.

그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-)

 위 문장이 있기 때문에 메모이제이션을 사용할 수 있다.

 

메모이제이션을 사용하려면 최적 부분 구조가 성립해야 한다. 대부분의 이런 경로 찾기 문제는 이전 경로에 따라 다음 경로가 영향을 받기 때문에 이런 식으로 풀 수 없다. 하지만 저 문장 때문에 이 문제는 가능하다. 조금 더 자세히 살펴보자.

 

 

허접해보이지만 처음에 a 위치에 판다가 있다고 하자. 그리고 v[a] < v[c] 이기 때문에 c로 이동했다.

 

다시 c의 위치가 시작점이 됐다. c에서 갈 수 있는 다음 영역에서 a는 무조건 제외된다. 이전 조건으로 인해 v[a] < v[c]이기 때문이다. 

이 점은 시사하는 바가 크다.

 

만약 a에서 출발해서 c로 가는게 아니라 애초에 c에서 출발한다면 어떨까?  이 상황은 a에서 c로 온 상황과 다르지 않다. 갈 수 있는 경로들의 가능성이 완벽하게 동일하다. 이 점이 이전 경로에 상관없이 최적 부분 구조를 가능하게 만든다. 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/*
욕심쟁이 판다
https://www.acmicpc.net/problem/1937
 */
public class Main {
	static int n;
	static int[][] forest,cache;
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		n = reader.readInt();
		forest = new int[n][n];
		cache = new int[n][n];
		for (int i = 0; i < n; i++) {
			Arrays.fill(cache[i], -1);
		}

		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < n; j++) {
				forest[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int ret = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ret = Math.max(ret, dfs(i,j));
			}
		}
		System.out.println(ret);
	}

	static int[] dr = {1,-1,0,0};
	static int[] dc = {0,0,1,-1};
	private static int dfs(int r, int c) {
		if(isStuck(r,c)) return 1;
		if(cache[r][c] != -1) return cache[r][c];

		int ret = 1;
		for (int i = 0; i < 4; i++) {
			int nextR = r+dr[i]; int nextC = c+dc[i];
			if(isRange(nextR, nextC)
					&& forest[nextR][nextC] > forest[r][c]) {
				ret = Math.max(dfs(nextR, nextC)+1, ret);
			}
		}
		return cache[r][c] = ret;
	}

	private static boolean isRange(int r, int c) {
		if(r < 0 || r >= n || c < 0 || c >= n) return false;
		return true;
	}

	private static boolean isStuck(int r, int c) {
		int hereAmount = forest[r][c];
		for (int i = 0; i < 4; i++) {
			int nextR = r+dr[i]; int nextC = c+dc[i];
			if(isRange(nextR, nextC) && hereAmount < forest[nextR][nextC]) return false;
		}
		return true;
	}

}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}