[BOJ] 1520번 내리막길 (C++)

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

1520번: 내리막 길

 

#include <iostream>
using namespace std;

int m, n;
int map[500][500];
int dp[500][500];

int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

int dfs(int x, int y) {
	if (x == m - 1 && y == n - 1) return 1;
	if (dp[x][y] != -1) return dp[x][y];

	dp[x][y] = 0;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
		if (map[nx][ny] >= map[x][y]) continue;

		dp[x][y] += dfs(nx, ny);
	}
	return dp[x][y];
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0);
	return 0;
}

 

단순 DFS로 풀면 시간 초과가 발생하기 때문에 DFS + DP로 구현하여 메모이제이션을 통해 시간을 줄여줘야 한다.

 

메모이제이션을 위해 int dp[][] 배열을 선언했다.

dp[a][b] = c는 "(a, b)에서 (m - 1, n - 1)까지 c개의 경로로 도달할 수 있다"를 의미한다.

 

특정 좌표에서 (m - 1,  n - 1)로 갈 수 있는 경로가 없는 경우에는 dp[][]에 0이 저장되므로 초기 dp배열의 모든 값들을 -1으로 초기화시켰다.