1520 - 내리막 길

문제풀이

처음에 문제를 보고 백트래킹을 생각했으나 N,M범위가 500으로 엄청 커서 백트래킹은 아니라고 생각했고, dfs bfs를 이용하여 탐색하자니 중복된 곳에 또 방문할 수 있어 visitied배열을 사용하지 못하여 많은 양의 계산을 하게 된다고 생각하여서 dp+dfs를 이용하였습니다.

1. dp[i][j] : (i,j)에서 (N,M)까지 c개의 경로로 도달할 수 있다.
2. dp를 모두 -1로 초기화한 이유
   dp를 0으로 초기화하면 어느 한공간에서 상하좌우로 이동할 수 없을 때에도 dp=0이므로 겹치게 된다.

   의미
   dp[i][j]=-1 // 아직 탐색 안함
   dp[i][j]=0 // 상하좌우로 갈 수 없습니다.

코드

#include <iostream>
using namespace std;

int map[501][501];

int M, N;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ans;
int dp[501][501]; // dp[i][j] : (i,j)에서 (N,M)까지 c개의 경로로 도달할 수 있습니다.

int dfs(int x, int y) {
	if (x == M && y == N) {
		return 1; // 도착지점에 도착했으므로 방법이 하나 있는 것이다. return 1
	}
	if (dp[x][y] != -1) { return dp[x][y]; } // -1이 아니면 이미 계산한 결과를 가지고 있으므로 
											// 계산한 결과를 return해줍니다.
	dp[x][y] = 0; // 탐색했다는 표시 아직 값이 더해지지 않음
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (map[x][y] > map[nx][ny] && nx<= M &&ny <= N &&nx >=1 && ny >=1 ) {
			dp[x][y]+=dfs(nx, ny); // return 하면서 경로수를 더해주기
		}
	}
	return dp[x][y]; // 경로수 리턴
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> M >> N;
	for (int i = 1; i <=M; i++) {
		for (int j = 1; j <=N; j++) {
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(1, 1);;
    return 0;
}