[C++] 백준 1520 내리막

#include <iostream>
#include <algorithm>
 
int M = 0;
int N = 0;
int dirX[4] = {1,-1,0,0};
int dirY[4] = {0,0,1,-1};
int arr[501][501] = {};
int DP[501][501] = {};
 
int DFS(int x, int y)
{
	if (x == M - 1 && y == N - 1) 
		return 1;
 
	if (DP[x][y] != -1) 
		return DP[x][y];
 
	DP[x][y] = 0;
 
	for (int i = 0; i < 4; ++i)
	{
		int nextx = x + dirX[i];
		int nexty = y + dirY[i];
 
		if (nextx >= 0 && nextx < M && 
			nextx >= 0 && nexty < N)
		{
			if (arr[nextx][nexty] < arr[x][y])
			{
				DP[x][y] = DP[x][y] + DFS(nextx, nexty);
			}
		}
	}
 
	return DP[x][y];
}
 
int main()
{
	std::cin >> M >> N;
 
	for (int i = 0; i < M; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			std::cin >> arr[i][j];
			DP[i][j] = -1;
		}
	}
 
	std::cout << DFS(0, 0);
 
	return 0;
}

일반적인 BFS로 풀려고 했으나 시간초과였습니다.

이유는 같은 장소를 여러 번 찾아야하기 때문입니다.

visit을 사용하지 않고 모든 경우의 수를 사용하는 경우에는 시간초과가 나올 수 밖에 없습니다.

그렇기 때문에 DP를 사용해야 합니다.

첫 경로에서 부터 마지막 경로까지 간 경우의 수를 구해서 적립하고 다른 경우에 수도 있는지 계속해서 나아가는 수를 구해야합니다.