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

문제는 다음과 같다.

오늘은 백준1520번 내리막 길 문제를 풀어보도록 하자. DFS와 DP를 이용한 문제이다. TOP-DOWN방식으로 구현을 해보았다. dp배열은 방문의 여부를 체크하기 위해 -1로 초기화를 해주었다. -1이면 방문하지 않은 것이고 0이면 방문을 한 것이다.

만일 이 문제를 DFS만으로 구현을 한다면 N,M이 500이었을 때 O(4^250000)의 시간복잡도를 갖게된다. 그러므로 TLE가 날 것이 뻔하다. 따라서 재귀함수를 이용한 TOP-DOWN 방식으로 메모이제이션을 하며 풀었다.

                                     [코드]
#include <iostream>
using namespace std;

int R, C;
int map[500][500];
int dp[500][500];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

int find_the_road(int y, int x) {
	if (y == R - 1 && x == C - 1) {
		return 1;
	}
	if (dp[y][x] == -1) {
		dp[y][x] = 0;
		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (my >= 0 && mx >= 0 && my < R && mx < C) {
				if (map[my][mx] < map[y][x]) {
					dp[y][x] += find_the_road(my, mx);
				}
			}
		}
	}
	return dp[y][x];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << find_the_road(0,0);
}