[BOJ] 1520번 : 내리막 길

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 }; 
int n, m; 
int a[505][505], d[505][505]; 

int dp(int x, int y) {
	if (d[x][y] != -1) return d[x][y];
	if (x == n - 1 && y == m - 1) return 1; 
	int& ret = d[x][y]; 
	ret = 0;
	for (int dir = 0; dir < 4; dir++) {
		int nx = x + dx[dir]; 
		int ny = y + dy[dir]; 
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 
		if (a[x][y] > a[nx][ny]) ret += dp(nx, ny);
	}
	return ret;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> m; 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j], d[i][j] = -1;
		}
	}
	cout << dp(0, 0);
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/1520.cpp

basic-algo-lecture/0x10/solutions/1520.cpp at master · encrypted-def/basic-algo-lecture

dp를 이용해서 풀었다. 하지만, bfs와도 매우 비슷한 느낌이 든다. 

나는 bfs로 풀려했지만, 시간초과가 날 것 같아 풀지 못했다. 

위 코드를 보면, dp함수에서 재귀적으로 호출한다. 

특정값에서 출발하여, 우측하단까지 가는 경우의 수를 결과적으로 출력하게 된다. 

이때, 이미 방문한 길(d [i][j]!= -1)은 return d [i][j]를 이용하여, 계산되었던 값을 반환한다. 따라서, 불필요한 계산을 줄일 수 있다. 

또한, d [x][y]의 참조자 변수를 두어, 값 수정을 가능하게 했다.