백준 1520번 내리막길

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

 

 

쉽지 않은 문제였다...

간단한 정규식으로 자신 기준 4방면에서 자신보다 높은 값이라면 그 지점까지 거쳐온 경우수들을 더해주는 방식으로 진행하였는데, 빼먹는 케이스가 생겼다.

따라서 탐색이 절대적으로 필요하다는 생각을 하게 되었다.

 

y,x에서 시작했을 때 가장 오른쪽에 도착하는 경우의 수를 search라고 한다.

당연히 y,x가 가장 오른쪽 좌표면 1을 반환한다.

만약 y,x에서 가장 오른쪽 도달 경우의 수를 구해놓은게 있다면 그것을 반환하면 된다.

위 두가지에 모두 해당되지 않는다면 경우의 수를 구해야한다. 

사방으로 움직일 수 있는 좌표에서 시작해서 오른쪽 아래로 도착하는 경우의 수를 현재 경우의 수에 모두 더해준다.

 

이때 주의 할 점은 구해놓은 경우의 수가 있다면 반환하는 과정에서 구해놓은 경우의 수가 0인경우가 존재할 수 있다.

이것을 또 반복하면 계속 같은 좌표를 반복하는 것이므로 -1이면 아직 경우의 수를 구해보지 않는 좌표고

구하기 직전에 0으로 갱신함으로 이 좌표는 결과가 0이든지 아니던지 그것이 답이라는 것을 의미한다.

따라서 -1이 아니면 경우의 수 구하기를 시작한다.

 

이렇게 처리하지 않으면 시간초과... 

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int N, M;
int arr[502][502];
int D[502][502];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

int search(int y, int x)
{
	if (y == N && x == M)
	{
		return 1;
	}
	if (D[y][x] != -1)
	{
		return D[y][x];
	}

	D[y][x] = 0;
	for (int i = 0; i < 4; i++)
	{
		int newy = y + dy[i];
		int newx = x + dx[i];
		if (arr[newy][newx] < arr[y][x] && newy > 0 && newy <= N && newx > 0 && newx <= M)
		{
			D[y][x] += search(newy, newx);
		}
	}
	return D[y][x];
}

int main(int argc, char** argv)
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> arr[i][j];
			D[i][j] = -1;
		}
	}

	
	cout << search(1,1) << endl;
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}