[BOJ 백준] 1937 - 욕심쟁이 판다

 

문제의 조건은 간단했지만 dp와 dfs가 합쳐진 문제였다. 처음에 dp같지 않은 dp를 사용했더니 시간초과가 발생했다.

 

dp[i][j]의 값을 i,j 위치에 판다가 있을 경우, 살 수 있는 최대일수 로 설정하였다.  

dfs의 탈출 조건을 설정해주는게 중요하다고 생각한다. 

 

if (dp[y][x] != 0)
		return dp[y][x];	

dp[y][x]가 0이 아니라는 것은 해당 위치에 판다가 놓여졌을 때 살 수 있는 최대일수가 결정되었다는 뜻이다.

 

그러므로, [y][x]위치에 방문을 하였을 때 살 수 있는 일수를 계산하지 않고 그 값을 사용하면 되는 것이다. 

 

 

 

소스코드

#include<iostream>
#include<algorithm>
#define endl "\n"
#define MAX 500
#define pii pair<int, pair<int,int>>
using namespace std;

int map[MAX][MAX];
int dp[MAX][MAX]; // i,j의 위치에서 판다가 있을 경우 살 수 있는 최대 날
int n;
int result = -1;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

int dfs(int y, int x) {		
	if (dp[y][x] != 0)
		return dp[y][x];	
    dp[y][x] = 1;
	for (int k = 0; k < 4; k++) {
		int ny = dy[k] + y;
		int nx = dx[k] + x;
		if (0 > ny || ny >= n || 0 > nx || 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];
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >>map[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dp[i][j] == 0) {
				result = max(result,dfs(i, j));
			}
		}
	}
	cout << result;
	return 0;
}