[백준OJ] 1520번 내리막 길

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

1520번: 내리막 길

---

 

풀이

dfs를 이용하여, 갈수있는 경우를 모두 구해주고 싶었지만 시간초과가 났다.

그래서 한번 방문한적이 있는 지점은 해당지점까지의 경로의 개수를 기억하는 DP를 이용하여 문제를 해결했다.

그런뒤 도착지점부터시작하면 자신보다 더 높은곳을 찾아주고, 시작지점부터 시작하면 자신보다 더 낮은곳을 찾아 진행시키면서, 목적지에 도달하면 1을 추가해주는 DP를 이용한 dfs를 해주면된다.

 

코드

#include<iostream>
#include <algorithm>
#include<memory.h>
using namespace std;

int maze[501][501];
int dp[501][501];
int mv[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int N, M;

int dfs(int x,int y) {
	if (dp[x][y] != -1) return dp[x][y];
	if (x < 0 || x >= N || y < 0 || y >= M) return 0;
	if (x == 0 && y == 0) return 1;

	dp[x][y] = 0;

	for (int i = 0; i < 4; i++) {
		int nx = x + mv[i][0];
		int ny = y + mv[i][1];

		if(maze[x][y] < maze[nx][ny]) {
			dp[x][y] += dfs(nx, ny);
		}
	}
	return dp[x][y];
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> maze[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	cout<<dfs(N-1,M-1);
	return 0;
}