백준 1520 내리막 길

백준 1520
그냥 dfs로 풀면 시간 초과가 발생한다. dp를 이용해 메모이제이션을 사용해서 시간을 줄여줘야 한다.
이 때 vis[i][j]이라는 dp 배열을 선언했다. 이 값은 (i,j) 좌표에서
(n-1,m-1) 좌표까지 도달 가능한 경로의 갯수이다.
vis 배열을 모두 -1로 초기화 한다. 이 의미는 아직 탐색하지 않았다는 뜻이다. 탐색을 했을 때 경로의 갯수가 0인 값과 구분해줘야 한다. 만약 중복해서 방문하게 되면 이미 탐색 완료 했기 때문에 (vis 배열이 -1이 아니기 때문에 ) 값을 가져다 쓰면 된다.

#include<bits/stdc++.h>
using namespace std;
int m, n;
int board[501][501];
int vis[501][501];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int dfs(int x,int y) {

	if (x == m - 1 && y == n - 1) return 1;
	else if (vis[x][y] == -1) {
		vis[x][y] = 0;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;

			if (board[x][y] > board[nx][ny]) vis[x][y] += dfs(nx, ny);
		}
	}
	return vis[x][y];
}
int main() {

	ios::sync_with_stdio(0); cin.tie(0);

	cin >> m >> n;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
			vis[i][j] = -1;
		}
	}

	cout << dfs(0, 0) << '\n';
}