백준 1520 - 내리막 길

문제링크

• 백준 1520

문제설명

문제접근

• DFS + DP 로 해결한다.
  • DFS 로 완전탐색을 할 수도 있지만 모든 칸에서 4개의 방향으로 탐색할 때 최악의 경우 4 x 500 x 500 만큼의 시간이 필요하므로 시간 초과에 걸린다.
  • 이미 알고 있는 경로는 탐색하지 않는 메모이제이션 기법을 활용한다.
• dist[r][c] 는 (r,c) 위치에서 목적지 (M, N) 까지 도달하는 경우의 수가 담긴다. dist[r][c] == -1 인 경우 (r,c) 에서 목적지 (N, M) 까지 경로를 탐색한 적이 없다는 것을 의미한다.

구현

#include <iostream>
#include <vector>
#include <memory.h>

#define MAX 501
using namespace std;

int M, N;
int board[MAX][MAX];
int dist[MAX][MAX];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int dfs(int cxpos, int cypos)
{
    // 목적지에 도달한 경우
	if (cxpos == M && cypos == N) return 1;
    // 이미 목적지까지 도달하는 경우의 수가 정해진 경우
	if (dist[cxpos][cypos] != -1) return dist[cxpos][cypos]; 

	dist[cxpos][cypos] = 0;
	for (int dir = 0; dir < 4; dir++)
	{
		int nxpos = cxpos + dx[dir];
		int nypos = cypos + dy[dir];
		if (nxpos < 1 || nxpos > M || nypos < 1 || nypos > N) continue;
		if (board[cxpos][cypos] <= board[nxpos][nypos]) continue;
		dist[cxpos][cypos] = dist[cxpos][cypos] + dfs(nxpos, nypos);
	}
	return dist[cxpos][cypos];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> M >> N;
	for (int r = 1; r <= M; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			int height;
			cin >> height;
			board[r][c] = height;
		}
	}
	memset(dist, - 1, sizeof(dist));
	int ans = dfs(1, 1);
	cout << ans << endl;
}