백준 C++ - 욕심쟁이 판다(1937) DFS, DP(memoization)

Memoization이란 (위키백과)

 - 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 수행을 제거하여 실행 속도를 빠르게 하는 기술이다. 

 - 동적 계획법의 핵심이 되는 기술 

 

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

1937번: 욕심쟁이 판다

 

0. 현재 위치의 탐색 횟수가 0으로 저장되어 있으면 1로 바꾸어준다.

1. (1, 1) 위치에서부터 상하좌우로 얼마큼 이동할 수 있는지 탐색하고, 더 이상 이동할 수 없으면 원래 처음 위치로 탐색 횟수를 기록하며 돌아간다.

 

2. 특정 위치에서 상하좌우로 나갈 때 탐색해야 할 방향에 탐색 횟수가 기록되어 있으면 탐색하지 않고 현재 위치의 탐색 횟수와 다음 방향 탐색 횟수를 비교한다.

 

3. 최댓값을 구하는 문제이므로 최댓값 갱신

#pragma warning(disable:4996)
#include <stdio.h>
#include <algorithm>
using namespace std;
int panda[510][510];
int dire[510][510];
int n, answer;

void dfs(int x, int y)
{
	if (x - 1 >= 1 && panda[x][y] < panda[x - 1][y]) // 상
	{
		if (dire[x - 1][y] == 0) // 다음 방향에 기록되어 있지 않으면 탐색 시작
		{
			dire[x - 1][y] = 1;
			dfs(x - 1, y);
		}
		dire[x][y] = max(dire[x][y], 1 + dire[x - 1][y]); // 1은 현재 위치에서 다음 방향으로 탐색하는 횟수이다.
	}

	

	if (x + 1 <= n && panda[x][y] < panda[x + 1][y]) // 하
	{
		if (dire[x + 1][y] == 0) // 다음 방향에 기록되어 있지 않으면 탐색 시작
		{
			dire[x + 1][y] = 1;
			dfs(x + 1, y);
		}
		dire[x][y] = max(dire[x][y], 1 + dire[x + 1][y]); // 1은 현재 위치에서 다음 방향으로 탐색하는 횟수이다.
	}



	if (y - 1 >= 1 && panda[x][y] < panda[x][y - 1]) // 좌
	{
		if (dire[x][y - 1] == 0) // 다음 방향에 기록되어 있지 않으면 탐색 시작
		{
			dire[x][y - 1] = 1;
			dfs(x, y - 1);
		}
		dire[x][y] = max(dire[x][y], 1 + dire[x][y - 1]); // 1은 현재 위치에서 다음 방향으로 탐색하는 횟수이다.
	}



	if (y + 1 <= n && panda[x][y] < panda[x][y + 1]) // 우
	{
		if (dire[x][y + 1] == 0) // 다음 방향에 기록되어 있지 않으면 탐색 시작
		{
			dire[x][y + 1] = 1;
			dfs(x, y + 1);
		}
		dire[x][y] = max(dire[x][y], 1 + dire[x][y + 1]); // 1은 현재 위치에서 다음 방향으로 탐색하는 횟수이다.
	}

}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &panda[i][j]);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (dire[i][j] == 0) dire[i][j] = 1; 
			dfs(i, j);
			if (answer < dire[i][j]) answer = dire[i][j];
		}
	}
	printf("%d", answer);
	return 0;
}