백준 1937 욕심쟁이 판다

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

욕심쟁이 판다 문제는 dfs와 dp를 활용하여 해결하는 문제이다. 한번도 방문하지 않은 점에서만 시작하여 다시 되돌아가며 dp의 value를 업데이트 해준다. 또한 dfs상 모든 정점을 돌게 되면 시간 초과가 발생하기 때문에 dp를 활용하여 중복되는 점이면 바로 return 시켜주저야한다. 

 

dp 값을 -1로 초기화 후 다음 정점으로 갈때 마다 1씩 더해준다. 한번도 방문한 적이 없는 값이 면 0을 반환해주고 아니면 그 값을 반환해준다. 

dp[nowY][nowX] = max(dp[nowX, nowY], dfs(nextY, nextX) + 1);

 

문제로 돌아가서 다음 칸이 클 때만 이동할 수 있다. 이건 단순히 값 비교를 통해 이동하면 된다. 

 

이 그림을 보면 0, 0에서 시작해서 차례대로 가는 것을 볼 수 있다. 그리고 아무 점도 갈 수 없을 때 재귀가 끝나며 값을 업데이트 해준다. 

 

여기서 (0,1)은 값이 작기 때문에 업데이트를 해주지 못해서 이 점부터 다시 dfs를 진행한다. 하지만 0, 0은 이미 방문한 적이 있기 때문에 dp[0][0]을 반환해준다. 따라서 dp[0][1]은 5가된다. 그리고 문제의 경우 끝점의 시작이 1부터 시작이라 답에 1을 더해주면 답이 된다. 

#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;

int map[502][502], dp[502][502], visit[502][502];
int ypos[4]= {0, 1, 0, -1}, xpos[4] = {1, 0, -1, 0};

int dfs(int y, int x, int day);

int N;
int main(){
	
	scanf("%d", &N);
	memset(dp, -1, sizeof(dp));

	for(int y = 0; y < N; y++)
		for(int x = 0; x < N; x++)
			scanf("%d", &map[y][x]);

	for(int y = 0; y < N; y++){
		for(int x = 0; x < N; x++){
			if(dp[y][x] == -1){
				dfs(y,x, 0);
			}
		}
	}	
	int maxValue = 0;

	for(int y = 0; y < N; y++){
		for(int x = 0; x < N; x++){
			if(maxValue < dp[y][x]){
				maxValue = dp[y][x];
			}
		}
	}

	printf("%d", maxValue+1);
}

int dfs(int y, int x, int day){
	if(dp[y][x] != -1)
		return dp[y][x];

	for(int i = 0; i < 4; i++){
		int nextY = y + ypos[i], nextX = x + xpos[i];

		if(map[y][x] < map[nextY][nextX] && nextY >= 0 && nextX >= 0 && nextY < N && nextX < N){	
			dp[y][x] = max(dfs(nextY, nextX, day+1) + 1, dp[y][x]);
		}
	}

	return dp[y][x] == -1? 0 : dp[y][x];
}