[BOJ] 1520 : 내리막 길 (C++) with Top Down DP

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

1520번: 내리막 길

걸린 시간 : 32분 21초

---

알고리즘

처음엔 간단한 DFS로 접근했다가 시간초과가 났다. 그제서야 시간복잡도를 체크해보니 최대 4^(500*500) 번의 실행이 일어날 수 있었다. 따라서 다른 방법을 찾아야 했다.

 

바로 떠올린 것이 DP였다. 예제를 다시 따라해보니 같은 실행을 너무 과도하게 반복한다는 생각이 들었다.

DP에서 제일 중요한 것은 일반항이다. 잘 적용할 수 있는 일반항을 생각해보았다.

pathcnt[i][j] 의 의미를 "(i, j) 에서 (M, N)까지 갈 수 있는 가짓수"로 생각할 수 있었다. 이러면 pathcnt[0][0]이 답이 될 것이다.

하지만, 기존에 많이 하던 방식으로 이 문제를 해결하려고 생각하니 또 뭔가 잘 안됐다... bottom up 방식으로 접근한다면, "어떤 지점부터 먼저 계산해야할 것인가" 가 문제였다. 따라서 top down 방식으로 해야 한다고 생각했다.

pathcnt 배열을 모두 -1로 초기화하고 가짓수를 알아냈을 땐 0이상의 수를 대입해서 중복된 계산을 하지 않도록 했다.

정답 코드

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

int M, N;
int board[501][501];
int pathcnt[501][501];
int di[4] = {-1, 0, 0, 1};
int dj[4] = {0, -1, 1, 0};

int bfs (int ci, int cj) {
	if (ci == M-1 && cj == N-1) {
		return 1;
	}
	if (pathcnt[ci][cj] != -1) {
		return pathcnt[ci][cj];
	}
	int ret = 0;
	for (int k = 0; k < 4; k++) {
		int ni = ci + di[k];
		int nj = cj + dj[k];
		if (ni < 0 || ni >= M || nj < 0 || nj >= N)
			continue;
		if (board[ni][nj] < board[ci][cj]) {
			ret += bfs(ni, nj);
		}
	}
	pathcnt[ci][cj] = ret;
	return ret;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	for (int i = 0; i < M; i++) {
		fill(pathcnt[i], pathcnt[i] + N, -1);
	}
	bfs(0, 0);
	cout << pathcnt[0][0];
	return 0;
}