[C++] BOJ-1520

 

 

문제풀이

---

1. 백트래킹 + DP를 이용해서 풀었다.

2. 재귀함수를 통해 모든 경우의 수를 백트래킹으로 탐색하지만 그 중에서 이미 탐색했던 부분이 있으면 그 곳은 다시 탐색하지 않는다.

 

3. 좌표(N,M)에 도착하면 결과값에 return값에 1씩 더해준다.

 

#include <iostream>
#include <cstring>

using namespace std;

int dx[4] = {0,0,-1,1}; // 상하좌우 
int dy[4] = {1,-1,0,0};

int arr[500][500];
int cache[500][500];

int N,M;

int func(int x, int y){	
	if(cache[x][y] != -1) return cache[x][y];
	if(x == M-1 && y == N-1) return 1;
	
	cache[x][y] = 0;
	for(int i = 0; i<4; i++){
		int rx = x + dx[i];
		int ry = y + dy[i];
		if(rx >= 0 && ry >= 0 && rx < M && ry < N && arr[x][y] > arr[rx][ry]){
			cache[x][y] += func(rx,ry);
		}
	}
	return cache[x][y];
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>> M >> N;
	
	memset(cache,-1,sizeof(cache));
	
	for(int i = 0; i<M; i++){
		for(int j = 0; j<N; j++){
			cin >> arr[i][j];
		}
	}
	
	cout << func(0,0);
}