[백준/C++] 1937. 욕심쟁이 판다

문제

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

풀이

저번에 풀었던 내리막길 문제와 비슷하게, DFS+DP 를 이용하면 풀 수 있는 문제였다.

bba-dda.tistory.com/entry/%EB%B0%B1%EC%A4%80C-1520-%EB%82%B4%EB%A6%AC%EB%A7%89-%EA%B8%B8

[백준/C++] 1520. 내리막 길

cache[i][j] : (i,j) 위치에서 시작할 경우 판다가 살 수 있는 날의 최댓값

즉, DFS 탐색과정중에, 이전에 탐색했던 좌표에 다시 도달할 경우, 다시 탐색하지 않고 cache값을 이용해서 경로의 개수를 알아내는 것이다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int forest[502][502] = { 0, };
int cache[502][502] = { 0, };

int dc[4] = { 0,0,-1,1 };
int dr[4] = { -1,1,0,0 };
int getMaxLiveDay(int i, int j) {
	if (cache[i][j])
		return cache[i][j];
	cache[i][j] = 1;
	for (int d = 0;d < 4;d++) {
		int newC = j + dc[d];
		int newR = i + dr[d];
		
		if (forest[newR][newC] > forest[i][j]) {
			cache[i][j] = max(cache[i][j], getMaxLiveDay(newR, newC)+1);
		}
	}
	
	return cache[i][j];
}
int main(void) {
	int n;
	cin >> n;
	
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			cin >> forest[i][j];
		}
	}
	int maxD = 0;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			maxD = max(maxD, getMaxLiveDay(i, j));
		}
	}
	cout << maxD;
	return 0;
}

 

결과