[C++] 백준 1520번 내리막 길

 

다이나믹 프로그래밍 문제입니다.

DFS나 BFS로만 풀게되면 시간초과가 발생합니다.

 

N * M 크기의 배열에서 숫자가 작아지는 길로만 이동해서

(0, 0) 에서 (N, M)의 위치까지 갈 수 있는 경우의 수를 찾는 문제입니다.

 

DFS방식으로 접근을 하고 (N, M)의 위치에 도착하면 성공한 경로의 memo값에 1을 더해줍니다.

다시 접근할 때 성공한 경로의 위치 중 한군데에 접근을 하면

성공한 경로의 memo값을 통해서 현재 경로의 값에도 값을 추가해줍니다.

이와 같은 방식으로 DFS와 DP를 통해 문제를 해결했습니다.

#include <iostream>
#include <cstring>
using namespace std;

int map[510][510];
int memo[510][510];
int moveX[4] = { 0, 1, 0, -1 };
int moveY[4] = { 1, 0, -1, 0 };
int M, N;

int search(int i, int j)
{
	if (i == M && j == N) {
		return 1;
	}
 	int &result = memo[i][j];

 	if (result != -1) {
 		return result;
 	}
 	result = 0;

	for (int k = 0; k < 4; ++k) {
		int x = i + moveX[k];
		int y = j + moveY[k];
		if (map[x][y] < map[i][j] && x > 0 && x <= M && y > 0 && y <= N) {
		result += search(x, y);
		}
	}
	return result;
}

int main(void)

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

 	memset(memo, -1, sizeof(memo));
 	cout << search(1, 1) << endl;
 	return 0;
}