[백준 1520] 내리막 길 (C++)

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

 

문제

---

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

 

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

  

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

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

dp+dfs 문제.

경로의 수를 저장하는 dp 배열을 생성하고, 배열의 (0, 0)에서부터 탐색한다. 방문했는지를 확인하기 위해 dp 배열은 -1로 초기화하고, 방문하지 않았다면 해당 위치에서부터 (N-1, M-1)까지 도달할 수 있는 경우의 수를 dp 배열에 기록한다.

 (i, j)에 위치했을 때 상하좌우에서 올 수 있는 경우의 수를 재귀함수를 통해 구하면 된다. 이미 이전에 기록한 적이 있다면 dp 배열에 기록되어 있는 값을 사용하면 된다.

 

아래는 코드.

#include <iostream>
#include <utility>
using namespace std;
int** arr;
int** dp;
int N, M;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int dfs(int x, int y)
{
	if (x == N - 1 && y == M - 1)
	{
		return 1;
	}
	if (dp[x][y] != -1)
	{
		return dp[x][y];
	}
	else
	{
		dp[x][y] = 0;
		for (int i = 0; i < 4; i++)
		{
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX == -1 || nextX == N || nextY==-1 || nextY == M)
			{
				continue;
			}
			if (arr[x][y] > arr[nextX][nextY])
			{
				dp[x][y] += dfs(nextX, nextY);
			}
		}
	}
	return dp[x][y];
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N >>M;
	arr = new int* [N];
	dp = new int*[N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[M];
		dp[i] = new int[M];
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			dp[i][j] = -1;
		}
	}
	cout << dfs(0, 0) << "\n";
	return 0;
}