[Baekjoon,1520] 내리막 길

첫 시작위치에서 시작하여 상하좌우 방향으로 이동가능한 경우 이동하다가 도착지점에 도착할 수 있는 경로의 개수를 찾아야 한다. 중복되어 계산되는 부분이 많으므로 메모이제이션을 적용하여 해결하면 된다. 이때 부분 문제를 아래와 같이 설정하면 된다.

getRouteNum(y,x) = 현재 위치가 (y,x)일 때 도착 지점까지의 경로 개수 

초기에 S(0,0)에서 B(2,3)까지 가는 경로가 2개이고 B에서 도착 지점 까지 가는 경로가 3개이면 2 x 3 = 6이라 위치마다 곱셈을 해야하는 줄 알았다. 하지만 아래의 구현된 코드를 보면 알 수 있듯이 B로 가는 각각의 경로에 3이라는 값이 주어져 3 + 3 = 6이 되기 때문에 각 위치마다 덧셈을 하는 것이 맞다.

구현

각 방향에 대한 상수를 선언하여 쉽게 접근하고 있다. 그리고 이동 시 높이가 낮아야만 이동 가능하기 때문에 이미 지나간 곳을 재방문 하는 경우는 없어 따로 처리하고 있지 않다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX=500;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};

int n,m;
int h[MAX][MAX];
int cache[MAX][MAX];

inline bool inRange(int y, int x)
{
    return 0<=y && y<n && 0<=x && x<m;
}

// 현재 위치 (y,x)에서 도착 지점까지 몇 개의 경로가 있는 지 반환 
int getRouteNum(int y, int x)
{
    // 범위를 벗어난 경우
    if(!inRange(y,x))
        return 0;
    // 도착한 경우 
    if(y==n-1 && x==m-1)
        return 1;
    
    int& ret=cache[y][x];
    if(ret!=-1)
        return ret;
    
    // 초기에는 길이 없다. 
    ret=0;
    // 상하좌우 모든 방향을 탐색한다.
    for(int dir=0;dir<4;++dir)
    {
        int ny=y+dy[dir];
        int nx=x+dx[dir];
        // 높이가 낮아야만 이동한다. 
        if(h[y][x]>h[ny][nx])
            ret+=getRouteNum(ny,nx);
    }
    return ret;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            cin>>h[i][j];
    memset(cache,-1,sizeof(cache));
    
    cout<<getRouteNum(0,0)<<endl;
    
    return 0;
}