[BOJ] 1520 - 내리막 길

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

---

[알고리즘풀이]

경로를 DFS로 역으로 탐색하며, 경우의 수를 저장한다.

dp[i][j] : (i , j )부터 목표 지점인 (0, 0)까지 가는 경우의 수.

이때, dp[i][j]에 밟아보지 않은 지점과 밟았는데 (0, 0)까지 가는 경로가 없는 경우를 구분해줘야 된다.

그렇지 않으면, 밟았던 경로도 다시 탐색하기 때문에 시간 초과에 걸린다.

따라서, 밟아보지 않은 지점에는 dp[i][j] = -1 을 저장하고, 경로가 없는 경우에는 dp[i][j] = 0이 저장되게,

dp[][] 배열을 -1로 초기화해줘야 한다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int N, M, map[500][500], dp[500][500];
int dir_x[4] = { -1,0,1,0 }, dir_y[4] = { 0, 1, 0, -1 };

int get_count(int, int);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << get_count(N - 1, M - 1);
}

int get_count(int i, int j) {
	if (dp[i][j] != -1)
		return dp[i][j];
	if (i == 0 && j == 0)
		return 1;
	dp[i][j] = 0;
	for (int k = 0; k < 4; k++) {
		int s_x = i + dir_x[k];
		int s_y = j + dir_y[k];
		if (0 <= s_x && s_x < N && 0 <= s_y && s_y < M && map[i][j] < map[s_x][s_y]) {
			dp[i][j] += get_count(s_x, s_y);
		}
	}
	return dp[i][j];
}

---