Baekjoon Review
[Gold 3] 1520 내리막 길
hanseongbugi
2024. 9. 23. 21:58
https://www.acmicpc.net/problem/1520
이 문제는 DFS와 DP를 혼합하여 접근해야한다.
DP를 사용해야하는 이유는 단순히 DFS만을 사용해 길을 찾게된다면
(N, M)까지 가는 모든 경로를 탐색해야 하기 때문에 목적지에 갈 수 없는 경우 시간 초과가 발생할 수 있다.
따라서 DP를 사용해 목적지에서부터 (0, 0)까지 경로를 저장하면 시간 내에 구할 수 있다.
처음 (0, 0)에서 상, 하, 좌, 우로 움직이며
이동할 칸의 값이 작다면 이동 가능한 칸으로 판단한다.
이동이 가능하다면 dp[0][0]에 이동 가능한 칸에 대한 경로를 모두 저장하게 된다.
따라서 dp[0][0]이 반환하는 값은 (0, 0)에서 (N, M)까지 갈 수 있는 모든 경로의 수를 저장하게 된다.
#include <iostream>
using namespace std;
int N,M;
int map[500][500];
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int dp[500][500];
int dfs(int y, int x){
if(y == N-1 && x == M - 1)
return 1;
if(dp[y][x] != -1)
return dp[y][x];
dp[y][x] = 0;
for(int i = 0;i<4;i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= N || nx < 0 || nx >= M)
continue;
if(map[ny][nx] >= map[y][x])
continue;
dp[y][x] = dp[y][x] + dfs(ny, nx);
}
return dp[y][x];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>N>>M;
for(int i = 0;i<N;i++){
for(int j = 0;j<M;j++){
cin>>map[i][j];
dp[i][j] = -1;
}
}
cout<<dfs(0,0);
}