[백준/c++] 1937번 - 욕심쟁이 판다

[ 문제 ]

 

 

 

[ 구현 ]

 

dfs+dp(메모이제이션)을 통해 풀 수 있다.

 

단순히 bfs/dfs를 돌리면 시간초과가 나는 이유는
한정된 점에 대해 돌리는 것이 아니라 모든 블록을 출발점으로 잡아서 한번씩 확인해봐야 하기 때문에 최악의 경우 O(N^4)이 나오기 때문이다.

우선 처음 출발하는 블록의 경우에 대해 방문한 블록 개수 1로 초기화 해주고

이미 방문한 블록이라면 dp배열에 저장해놓은 값을 바로 리턴

 

아니라면 

if (forest[nx][ny] > forest[x][y]) {
dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);}
을 통해 다음 블록이 더 많은 대나무를 가지고 있는지 확인하고
기존까지의 최대 블록 이동개수와 다음 블록을 통해 끝까지 나아갔을 때의 블록 이동개수를 비교하여

둘 중에 더 큰 값을 dp배열에 저장한다.

 

 

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,1,-1,0 };
int forest[501][501];
int dp[501][501];
int ans;

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


	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || ny < 0 || nx >= n || ny >= n)
			continue;

		if (forest[nx][ny] > forest[x][y]) {
			dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1);
		}

	}

	return dp[x][y];
}



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

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> forest[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ans = max(ans, dfs(i, j));
		}
	}

	cout << ans;

	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

dfs에 dp를 활용하여 효율적으로 탐색하는 방법을 배우기 좋은 문제였다.