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

https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

 

 

코드 설명

DP 메모리제이션 방식 + DFS을 합친 좋은 문제였던 것 같다.

어디 코테를 보면서 비슷한 걸 본 적이 있었는데 그 당시에 못 풀었어서 이문제는 복습을 계속해봐야 할 것 같다.

 

문제의 경우 DP맵 , 대나무 숲 맵 두 개로 나누어 서로 비교하며 문제를 풀어나가야 한다.

DP[y][x] : 그곳에서 시작하였을 때의 최대 이동 칸수 

즉, DP[y][x]에 값이 있다는 것은 굳이 들어가지 않아도 된다는 것을 의미한다. (이미 최대 경로가 들어가 있음)

 

이후에는 dfs(ny,nx)+1 을 통해 1씩 경로수를 늘려주며 재귀 탐색을 한다.

코드

//대나무먹고 자리옮기면 옮기려는 지역이 대나무가 더 많아야함(상하좌우)
//최댓값찾기
//전체탐색
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N;
int map[501][501];

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int dp[501][501];
int dfs(int y, int x) {
	
	if (dp[y][x]) return dp[y][x]; // dp map에 값이 있다면 탐색하지 않고 리턴
	dp[y][x] = 1; // 없으면 처음 1부터 시작

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		if (map[ny][nx] <= map[y][x]) continue;
		dp[y][x]= max(dp[y][x], dfs(ny, nx)+1);


	}

	return dp[y][x];  // 4방향 전부 작을때 기존 dp return


}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];

		}
	}

	int answer = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			answer = max(answer, dfs(y, x));
		}
	}

	cout << answer;



	return 0;
}