백준 - 1520번 : 내리막 길 (C++)

풀이 방법 : DP + DFS

목표 지점부터 시작하여 상하좌우에 해당하면서, 높이를 따져서 이동가능한 루트의 갯수를 누적해 합해주는 방식으로 구현하였다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int DirX[4] = { -1,1,0,0 };
int DirY[4] = { 0,0,-1,1 };

int DP(int y, int x, int N, int M
	, vector<vector<int>>& vecCnt
	, const vector<vector<int>>& vecBoard)
{
	if (vecCnt[y][x] != -1)
		return vecCnt[y][x];

	int Sum = 0;

	for (int i = 0; i < 4; ++i)
	{
		int NextY = y + DirY[i];
		int NextX = x + DirX[i];

		if (NextY < 0 || NextY >= N || NextX < 0 || NextX >= M)
			continue;

		if (vecBoard[NextY][NextX] > vecBoard[y][x])
		{
			if (vecCnt[NextY][NextX] == -1)
			{
				vecCnt[NextY][NextX] = DP(NextY, NextX, N, M,vecCnt, vecBoard);
			}

			Sum += vecCnt[NextY][NextX];
		}
	}

	vecCnt[y][x] = Sum;

	return Sum;
}

int main()
{
	int N, M;

	cin >> N >> M;

	vector<vector<int>> vecBoard;
	vector<vector<int>> vecCount;
	vecBoard.reserve(N);
	vecCount.reserve(N);

	for (int i = 0; i < N; ++i)
	{
		vector<int> vecRow;
		vector<int> vecRowCnt;
		vecRow.reserve(M);
		vecRowCnt.reserve(M);

		for (int j = 0; j < M; ++j)
		{
			int Num;
			cin >> Num;

			vecRow.push_back(Num);
			vecRowCnt.push_back(-1);
		}

		vecBoard.push_back(vecRow);
		vecCount.push_back(vecRowCnt);
	}
	
	vecCount[0][0] = 1;

	int Answer = DP(N - 1, M - 1, N, M, vecCount, vecBoard);

	cout << Answer << '\n';
}