백준 1520 내리막 길(c++)

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

1520번: 내리막 길

이 문제는 막연하게, DFS로 풀면 안됩니다. 높이, 너비가 500이기에 너비 우선 탐색으로만 풀려면 정말 오랜 시간이 걸리기 때문입니다. 그래서 (DP + DFS)로 풀 수 있습니다.

<코드> 

#include <iostream>
#include <cstring>

using namespace std;

int board[501][501];
int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int dp[501][501];
int n,m;
int cnt=0;

int dfs(int x, int y)
{
    if(x == m-1 && y == n-1)
    { 
        return 1;
    }

    if(dp[x][y]!= -1) return dp[x][y];
    else 
    {
        dp[x][y] = 0;
        for(int i=0;i<4;i++)
        {   
            int row = x + mov[i][0];
            int col = y + mov[i][1];
            
            if(row >= 0 && col >= 0 && row < m && col < n )
            {
                if(board[row][col] < board[x][y]) dp[x][y] += dfs(row,col);
            }
        }
    }
   

    return dp[x][y];

}


int main()
{
    
    cin>>m>>n;

    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>board[i][j];
        }
    }

    memset(dp,-1,sizeof(dp));
    

    cout<<dfs(0,0)<<'\n';
}

Test case 

입력(세로, 가로)

4 5

 

입력
50 45 37 32 30
35 50 40 20 25
30 30 25 17 28
27 24 22 15 10

 

출력
3

 

우선적으로 2차원 DP 배열을 -1로 초기화 해줘야 합니다. (-1 : 방문하지 않음, 0 : 방문)

DP(동적 계획법)을 사용한 이유는 예시를 들어, 50 -> 37로 갈 수 있는 경우의 수는 1개입니다 (50 -> 45 -> 37)

즉, 50(1행, 1열) -> 10(4행, 5열)로 가기 위한 경로값을 누적하기 위해 DP를 사용하였습니다.

 

DFS를 이용해서, 첫번째 그림을 보면, 50 -> 35 -> 30 -> 27 -> ... -> 10으로 이동했습니다. 10으로 이동하게 되면, 행열의 인덱스 값이 각각 m-1, n-1이 되므로 1을 리턴하게 됩니다. 두 번째 그림과 세번째 그림도 마찬가지로 오른쪽 가장 아래 지점까지 도착했기에, 1을 리턴해주고 DP배열에 값을 누적 시켜주게 됩니다. 그래서 경우의 수는 3개가 되므로 출력값이 3이 됩니다.