[BOJ] (C++) 1520 내리막 길

골드4 문제이며 DP와 DFS를 사용하는 문제.

주의할 점은 DP를 0이 아닌 -1로 초기화 해줘서 길이 없는건지 확인하지 않은건지 차이를 줘야함.

문제 링크 : 1520번: 내리막 길 (acmicpc.net)

#include <iostream>
#include <vector>

using namespace std;

int ROTATE_X[] = { -1, 1, 0, 0 };
int ROTATE_Y[] = { 0, 0, -1, 1 };

int DP[501][501];
int map[501][501];
int N, M;

int DFS(int row, int col)
{
	if (row == N && col == M)
		return 1;
	if (DP[row][col] != -1)
		return DP[row][col];

	DP[row][col] = 0;

	int next_row, next_col;
	for (int i = 0; i < 4; i++)
	{
		next_row = row + ROTATE_X[i];
		next_col = col + ROTATE_Y[i];

		if (next_row >= 1 && next_row <= N && next_col >= 1 && next_col <= M)
			if (map[next_row][next_col] < map[row][col])
				DP[row][col] += DFS(next_row, next_col);
	}

	return DP[row][col];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
			DP[i][j] = -1;
		}

	cout << DFS(1, 1) << '\n';

	return 0;
}