[BOJ] 1937 욕심쟁이 판다 C++

개요

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

1937번: 욕심쟁이 판다

골드급 DFS + DP 문제다.

풀이

처음에는 재귀를 활용한 DFS로 접근했다.

모든 구간에서 DFS로 탐색했고, 최대값을 구했다.

visited 배열에 판다가 이동한 값의 최대 값을 기록하며 가지치기 해줬다.

(다음 칸이 현재 칸보다 높은 값일 경우 continue)

하지만 결과는 시간 초과

 

행렬 기반 DFS는 O(V^2)다.

500*500을 25,000이라고 착각해서,,,, 25000^2 = 6억 이라서 가지치기좀 해주면 될 줄 알았다.

하지만 실제로는 600억이었고, 당연히 시간 초과였다.

 

가지치기로는 어림도 없는 숫자였고 DP를 통해 풀어내야했다.

dp에 판다가 이동한 값 말고 이동할 값의 최대치를 넣어주면 된다.

빨간 색 화살표를 따라 탐색한 후 파란 색 화살표로 돌아온다.(+1 후 return)

비교할 값이 생기면 초록색 처럼 더 큰 값에 +1을 하여 돌려주면 된다.

위 방식으로 모든 칸을 탐색하면 된다.

 

떠올리기는 어렵지 않았는데, 재귀에 익숙하지 않아서 구현에 좀 오래걸렸다.

코드

#include<iostream>
using namespace std;
constexpr int LIMIT = 502;
constexpr int dy[] = { 0,0,-1,+1 };
constexpr int dx[] = { -1,+1,0,0 };

int n;
int block[LIMIT][LIMIT];
int dp[LIMIT][LIMIT];
int ans;

int DFS(int y, int x)
{
	if (dp[y][x]) return dp[y][x];
	dp[y][x] = 1;
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (block[ny][nx] <= block[y][x]) continue;
		dp[y][x] = max(dp[y][x], DFS(ny, nx) + 1);
	}
	return dp[y][x];
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> n;
	for (int j = 1; j <= n; j++)
		for (int k = 1; k <= n; k++)
			cin >> block[j][k];

	for (int j = 1; j <= n; j++)
		for (int k = 1; k <= n; k++)
			ans = max(ans, DFS(j, k));
	
	cout << ans;
}