[PS] 백준 #1520 내리막 길 문제 풀이

[ 문제 풀이 ]

• Problem : 백준 #1520
• 구분 : DP(다이나믹 프로그래밍)
• 난이도 : Gold 4
• 풀이 방법 :
  • 해당 문제는 (1,1)에서 출발하여, (M,N)까지 상,하,좌,우 방향에서 내리막길로만 간다는 데에 힌트가 있습니다.
  • 단순히 생각해보면 (M,N)에 도착할때까지 내리막길인 경우를 모두 재귀로 돌려서 세어주는 방법이 있지만, 이는 최악의 경우 O(4^n)정도 되기때문에 비효율적입니다.
  • 다른 효율적인 방법도 있겠지만, 저는 Caching(메모이제이션)을 활용한 DP로 해결하였습니다.
    
    
  • 현재 위치에서 도착지까지 가는 경로의 수를 D(x,y)라고 한다면, D(x-1,y), D(x+1,y), D(x,y-1), D(x,y+1) 중에서 (x,y)가 좌표 내 범위에 있고, 내리막길인 지점인 값들을 더해주시면 됩니다.
  • 경로를 찾아가는 도중에 내리막길이 없으면 0을 return 하면되고, 도착지에 도달했을 경우 1을 return 해주면 모든 경로의 수를 구할 수 있습니다.
  • 자식노드는 중복으로 호출되므로 Caching을 해주셔야 효율적으로 처리할 수 있습니다.
  • 시간복잡도는 O(n*m)입니다.

[ 🤟🏻 Code from ss-won ]

#include <iostream>
#include <algorithm>
#include <functional>
#define MAX 500
using namespace std;
int m, n;
int map[MAX][MAX];
int memo[MAX][MAX];
pair<int,int> mv[4] = {{-1,0},{1,0},{0,-1},{0,1}};

int getpaths(int x, int y){
   if(x < 0 || y < 0) return 0;
   if(x == m-1 && y == n-1){
       return 1;
   }
   if(memo[x][y] != -1) return memo[x][y];
   memo[x][y] = 0;
   for(int i=0;i<4;i++){
       int nx = x+mv[i].first, ny = y+mv[i].second;
       if(nx >= 0 && nx < m && ny >= 0 && ny < n){
           if(map[x][y] > map[nx][ny]){
               memo[x][y] += getpaths(nx,ny);
           }
       }
   }
   return memo[x][y];
}

int main() {
   ios_base :: sync_with_stdio(false);
   cin.tie(NULL);
   cin >> m >> n;
   for(int i=0;i<m;i++){
       for(int j=0;j<n;j++){
           cin >> map[i][j];
       }
   }
   
   for(int i=0;i<m;i++){
       fill(&memo[i][0], &memo[i][n-1]+1, -1);
   }
   cout << getpaths(0, 0);
}