[BOJ] 백준 1520번: 내리막 길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

dp 문제입니다. 다만, 가능한 이동방향이 "상하좌우"이므로 bottom-up 방식으로 탐색하기엔 어려움이 있습니다.

따라서 top-down 방식으로 구현하였습니다.

 

#include <bits/stdc++.h>
using namespace std;

int M, N, a[501][501], cache[501][501];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int solve(int y, int x){
	if(y < 1 || y > M) return 0;
	if(x < 1 || x > N) return 0;
	if(y == 1 && x == 1) return 1;
	
	int &ret = cache[y][x];
	if(ret != -1) return ret;
	ret = 0;
	
	for(int i = 0; i < 4; i++){
		int cy = y + dy[i];
		int cx = x + dx[i];
		if(cy < 1 || cy > M) continue;
		if(cx < 1 || cx > N) continue;
		if(a[y][x] < a[cy][cx]) ret += solve(cy, cx);
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> M >> N;
	
	for(int i = 1; i <= M; ++i){
		for(int j = 1; j <= N; ++j){
			cin >> a[i][j];
		}
	}
	
	memset(cache, -1, sizeof(cache));
	cout << solve(M, N);
}

 

캐싱을 통해 값이 이미 계산되어 있다면 바로 그 값을 return합니다.

(memset을 이용해 cache 배열의 값을 -1로 초기화한 후, 값을 새로 계산할 때에는 -1은 배열의 새로운 값으로 저장되지 않으므로 -1이 아닐 경우 새로 계산된 값임을 알 수 있습니다.)

 

"상하좌우" 4방향 탐색의 경우 아래와 같이 dx[4], dy[4] 배열을 활용하고

8방향 탐색의 경우 dx[8], dy[8] 배열을 활용하면 좋습니다.