[BOJ 1937] 욕심쟁이 판다

풀이

현재 팬더 위치에서 4방향을 스캔하면서 대나무가 더 많은 쪽으로 이동하도록 구현함 DFS로만 하게되면 같은 경로를 반복해서 조사하기 때문에 시간초과가 발생한다 그래서 한번 갔던 경로는 최대 길이를 저장하면서 DFS를 진행한다.

코드

#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
#include <fstream>

using namespace std;

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

int n;
int Map[501][501];
int dp[501][501];


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

	ret = 0;

	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  || Map[y][x] >= Map[ny][nx]) continue;

		ret = max(ret, dfs(nx, ny) + 1);
	}
	return ret;
}

int main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	//fstream fs("1.in");

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

	memset(dp, -1, sizeof(dp));

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

	cout << ans + 1;

	return 0;
}