백준 1520 내리막길

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

1520번: 내리막 길

 

 

 

EXPLANATION

 

DFS를 이용해서 풀면 된다.

첫 지점부터 목표지점으로 가는 길을 찾아가자.

어느 지점에서 갈 수 있는 길이 여러개 나오면 하나씩 먼저 갈 수 있는데 까지 갔다가 돌아온다.

목표 지점을 찍었다면 그 길을 돌아오면서 지나온 지점들에서 목표 지점까지 갈 수 있는 길의 횟수에 1을 더해주면된다.

 

 

ex)

예제 입력

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

 

지나간 길은 지나갔다고 표시.

길을 돌아오면서 지나온 지점들에서 목표 지점까지 갈 수 있는 길의 횟수에 1을 더함.

 

 

return DP[0][0] = 3

 

 

CODE

#include<iostream>
#define MAX 500
using namespace std;

int N, M, ans;
int MAP[MAX][MAX];
int DP[MAX][MAX];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };


int DFS(int x, int y)
{
    if (x == N - 1 && y == M - 1) return 1;
    if (DP[x][y] != -1) return DP[x][y];

    DP[x][y] = 0;    //온 길 체크.
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < M)
        {
            if (MAP[nx][ny] < MAP[x][y])
            {
                DP[x][y] = DP[x][y] + DFS(nx, ny);
            }
        }
    }
    return DP[x][y];
}



int main(void)
{
    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;    //dp 초기화
        }
    }
    
    ans = DFS(0, 0);    //DP[0][0];
    cout << ans << "\n";

    return 0;
}