백준 1520: 내리막 길

문제 요약

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

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

문제 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• DFS

문제 풀이

주어진 조건에 따라 2차원 배열을 순회하는 가짓수를 파악하는 DP문제이다. 여기서 DP는 2차원 배열을 사용하였고, DFS로 탐색해 나가면서 DP배열을 구축해나갔다.

dfs()에서는 i,j에서 상하좌우 1칸씩 보고, 해당 칸이 현재 칸보다 작은 경우 재귀호출 하는것으로 구현하였다. 여기서 그 결과를 현재 결과에 누적시킨다. 현재 칸(i, j)가 (n-1, m-1)이면 탐색을 완료한 것이므로 1을 반환한다. 한 가지의 가짓수를 발견한 것이다. 이렇게 하여 dp배열의 (0,0)을 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int n, m;
int ary[500][500], dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }, dp[500][500];

int dfs(int i, int j) {
	if (i == n - 1 && j == m - 1) return 1;
	if (dp[i][j] != -1) return dp[i][j];
	dp[i][j] = 0;
	for (int k = 0; k < 4; k++) {
		int ni = i + dir[k][0];
		int nj = j + dir[k][1];
		if (ni >= 0 && ni < n && nj >= 0 && nj < m) {
			if (ary[i][j] > ary[ni][nj])
				dp[i][j] += dfs(ni, nj);
		}
	}
	return dp[i][j];
}

int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &ary[i][j]);

	cout << dfs(0, 0);
}