[BOJ] 1937 - 욕심쟁이 판다

안녕하세요.
여행벌입니다.

오늘은 BOJ 1937번 욕심쟁이 판다 문제를 다뤄보겠습니다.

Dp 와 DFS 를 조합해야 해결할 수 있는 문제로 까다로운 문제입니다.

---

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

1937번: 욕심쟁이 판다

[알고리즘풀이]

가장 먼저 생각나는 방법은 모든 곳에서 DFS 탐색을 진행하며, 가장 오래 살아남는 값을 구하는 방법입니다.

단순하고 정확하지만 시간초과에 걸립니다.

따라서 DFS 탐색을 진행하며, 더 이상 탐색을 진행하지 않아도 되는 경우에 한해서는 가지치기를 해줘야 합니다.

이를 위해 메모이제이션을 이용합니다.

똑같이 모든 곳에서 DFS 탐색을 진행해나가는데, DFS 탐색을 하며 그 지점에서 가장 오래 살아남는 값을 저장해나갑니다.

그러다 이미 탐색이 완료된 지점(값을 저장한 곳)에 방문하게 되면 더 이상 탐색을 진행하지 않고도

가장 오래 살아남는 값을 도출해낼 수 있으므로 탐색을 종료하면 됩니다.

#include<iostream>
#include<algorithm>

using namespace std;

int n;
int map[500][500];
int dp[500][500];

int d_x[4] = { -1,0,1,0 };
int d_y[4] = { 0,-1,0,1 };

int DFS(int, int);

int main(void) {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			ans = max(ans, DFS(i, j)); // 지금까지 나온 값 중 가장 큰 값을 저장.
	cout << ans;
}

int DFS(int x, int y) {
	if (dp[x][y]) // 이미 탐색이 완료된 지점이라면 종료
		return dp[x][y];
	dp[x][y] = 1; // 아니라면 1부터 탐색 진행.
	for (int i = 0; i < 4; i++) {
		int n_x = x + d_x[i], n_y = y + d_y[i];
		if (0 <= n_x && n_x < n && 0 <= n_y && n_y < n)
			if (map[x][y] < map[n_x][n_y])
				dp[x][y] = max(dp[x][y], DFS(n_x, n_y) + 1);
	}
	return dp[x][y];
}

---