내리막 길(DFS+DP)

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

1520번: 내리막 길

 

단순 DFS로만 알고리즘을 짜게되면 시간초과가 발생하게 된다

 

이전에 목표까지 도달했던 경로를 저장하여 추후 재도달시 바로 목표까지 도달한다고 판단하는

다이나믹 프로그래밍 기법을 사용해야 한다.

 

#include <iostream>
#include <stack>
using namespace std;

int x, y;
// input
int Matrix[500][500] = { 0, };
// 경로를 가짓수로 저장(DP)
int Check[500][500] = { 0, };
int xpos[4] = { 0, 1, 0, -1 };
int ypos[4] = { 1, 0, -1, 0 };

bool check(int nx, int ny)
{
	if (nx >= 0 && nx < x && ny >= 0 && ny < y) return true;
	else return false;
}

int DFS(int cx, int cy)
{
	// 목표지점이면 1 반환
	if (cx == x - 1 && cy == y - 1) return 1;
	// 이미 이전에 도달했던 경로라면 저장된 값을 반환(DP)
	if (Check[cx][cy] != -1) return Check[cx][cy];

	// 방문판단을 위해 -1로 초기화 했으므로 현재 경로를 0으로 초기화
	Check[cx][cy] = 0;
	for (int i = 0; i < 4; i++)
	{
		int movex = cx + xpos[i];
		int movey = cy + ypos[i];
		if (check(movex, movey))
		{
			if (Matrix[cx][cy] > Matrix[movex][movey])
			{
				// 현재 값 + 다음 노드에 대한 DFS
				Check[cx][cy] += DFS(movex, movey);
			}
		}
	}

	// 네 방향에 대해 경로탐색을 모두 끝냈다면
	// 자기 자신을 반환(현재 위치부터 목표까지 도달하는 경우의 수)
	return Check[cx][cy];
}

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

	cin >> x >> y;

	for (int i = 0; i < x; i++)
	{
		for (int j = 0; j < y; j++)
		{
			cin >> Matrix[i][j];
			Check[i][j] = -1;
		}
	}

	if (x == 1 && y == 1) Check[0][0] = 1;
	else DFS(0, 0);

	cout << Check[0][0] << '\n';
}