[C++] 백준 1520 : 내리막 길

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

1520번: 내리막 길

백준 1520번 내리막 길을 풀었다.

 

처음엔 DFS와 visited배열을 사용해서 백트래킹으로 문제를 풀었는데 시간 초과가 나왔다.

이것 저것 시도하다가 검색을 해보니 DP를 같이 사용해서 풀면 된다고 나와 있었다.

DP를 사용하면 이미 계산했던 경로는 DP배열에서 값을 얻어오니까 훨씬 빠르게 문제를 해결할 수 있다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int m, n;
int map[500][500];
int dp[500][500];

int DFS(int x, int y) {
	if (x == m-1 && y == n-1) {
		return 1;
	}
	else if (dp[x][y] == -1) {
		dp[x][y] = 0;
		for (int i = 0; i < 4; i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];

			if (next_x >= 0 && next_x < m
				&& next_y >= 0 && next_y < n) {
				if (map[x][y] > map[next_x][next_y]) {
					dp[x][y] += DFS(next_x, next_y);
				}
			}
		}
	}

	return dp[x][y];
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j < 500; j++)
			dp[i][j] = -1;
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}


	DFS(0, 0);
	cout << dp[0][0];

	return 0;
}