[백준/BOJ] 백준 1937번 : 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

판다가 (x, y) 위치에 있을 때 살 수 있는 일수를 구하는 함수를 통해, 모든 위치를 확인해 그중 가장 큰 값인 가장 오래 사는 일수를 구한다

 

코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int board[500][500];
int cache[500][500];
int dx_dy[4][2] = { {0,-1}, {-1,0}, {0,1}, {1,0} };

//판다가 (x,y)위치에 있을때 살 수 있는 일 수를 구한다
int Solve(int x, int y)
{
	//기저 사례(판다가 더이상 갈 곳이 없을때)인지 확인한다
	bool finish = true;
	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(x + dx_dy[i][0], y + dx_dy[i][1]);
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] > board[x][y])
		{
			//판다가 갈곳이 있으므로 끝이 아니다
			finish = false;
			break;
		}
	}

	//기저 사례라면 현재 일수 1을 반환한다
	if (finish)
		return 1;

	int& ret = cache[x][y];

	//판다가 (x,y)위치인 경우를 구한적 있을때
	if (ret != -1)
		return ret;

	ret = -987654321;

	//인접한 부분 중 갈 수 있는 부분으로 가서 그 위치에서 있을때 살수 있는 일수 + 1(현재 일수)중 최대를 찾는다
	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(x + dx_dy[i][0], y + dx_dy[i][1]);
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] > board[x][y])
		{
			ret = max(ret, Solve(there.first, there.second) + 1);
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp;
	int result = 0;

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

	cin >> n;

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


	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			//판다가 (i,j)에 있을때 사는 수명을 구해 그중 최대로 살 수 있는 일수를 구한다
			result = max(result, Solve(i, j));
		}

	cout << result;

	return 0;
}