백준 1937 욕심쟁이 판다 c++ - dp ,dfs

지금보다 많이 먹길 원하는 돼지 판다의 일생을 계산해보자.

 

문제의 조건은 다음과 같다.

1. 판다는 상하좌우로 움직인다.

2. 지금 칸의 대나무보다 이동하려는 칸의 대나무가 많을 때만! 이동한다.

3. 갈 곳이 없으면 굶어죽는다.(일생이 끝난다.)

4. 크기는 500x500 이며, 대나무의 최대값은 100만보다 같거나 작다.

 

처음 문제를 접근한 방법은 다음과 같다.

1. BFS 혹은 DFS로 모든 좌표에서 완전탐색을 실시하여 최댓값을 구한다.

 

완전탐색시에 발생하는 문제는 다음과 같다.

1. 시간 초과

 

최적화 방식은 다음과 같이 시도했다.

1. 특정 좌표의 상하좌우 중 자기보다 큰 값이 없을 때(국소 최소값)만 탐색을 시작.

2. visited 배열에 탐색하면서 들렀던 곳과 그 일생(ex. 3일)을 기록해두고, 지금보다 일생이 길었다면 탐색하지 않는다.

3. priority queue를 사용해 가장 작은 값을 가지는 좌표부터 순차적으로 진행

 

결과는 전부 Time limit exceed가 떴다.

 

어쩔 수 없이 DP로 접근하기로 했다.

DP가 필요했던 이유는 다음과 같다.

1. 특정 지점에서 과거에 들렀던 다른 좌표로 이동하고 싶을 때,

그 지점에서 최대로 오래 살 수 있는 날은 며칠인지 기록해둬야

탐색을 그만 두고 그대로 더해서 계산할 수 있다.

 

DP의 접근 방식은 다음과 같다.

1. 특정 좌표를 정한다.

2. 갈 수 있는 위치를 정한다. (대나무가 더 많고 상하좌우 중 하나일 것)

3. DFS로 탐색해 들어간다.

4. 가장 멀리 간 지점에서(최종 도착점) 살 수 있는 날은 단 하루이다.

5. 그 직전 지점(가장 먼 곳에서 하루 전)에서 살 수 있는 날은 이틀이다.

6. 계속해서 dfs를 빠져나오면서 dp배열에 저장한다.

(예를 들어 (1,2)에서 가장 멀리 간 곳이 5일과 3일 둘이라 가정하면 ,(1,2)에서는 5를 저장한다. )

7. 특정 좌표에서 최대로 살 수 있는 날을 구한다.

8. 모든 좌표에 대해 수행한다.

9. 내가 가려는 좌표에 이미 최대로 살 수 있는 날이 정해져있다면, 지금 내 최대값과 비교하여 큰 수를 저장하고 종료한다.

 

전체코드

#include <stdio.h>
#include <algorithm>
using namespace std;
int n, Map[501][501];
//최대로 살 수 있는 날 저장해두는 배열
int dp[501][501];
int ans;
int dy[] = { 0,0,-1,1 }, dx[] = { -1,1,0,0 };

//dp+dfs
int dfs(int y, int x) {
	//이미 과거에 최대로 살 수 있는 날을 구했다면 바로 리턴
	if (dp[y][x]) return dp[y][x];
    //구하지 않았다면 최소 하루는 살 수 있으므로 1부터 시작
	dp[y][x] = 1;
	for (int i = 0; i < 4; i++) {
    //갈 수 있는 방향
		int ny = y + dy[i];
		int nx = x + dx[i];
        //대나무가 더 많다면
		if (Map[ny][nx] > Map[y][x]) {
        //y,x에서 살 수 있는 최대 일수 저장
        //ny, nx 에서 살 수 있는 최대값 +1 (내 쪽에서 하루 이동하므로 +1해준 것)
        //위와 현재 저장된 값을 비교하여 최대로 살 수 있는 날을 저장.
			dp[y][x] = max(dp[y][x], dfs(ny, nx) + 1);
		}
	}
    //저장했다면 그 좌표에서 살 수 있는 최대일수 리턴
	return dp[y][x];
}


int main() {
//입력
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &Map[i][j]);
		}
	}
//모든 좌표에서 탐색 수행
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans = max(ans,dfs(i, j));
		}
	}
	printf("%d", ans);
}