[ 백준 1520 ] 내리막길 (C++)

백준의 내리막길(1520) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 시작점에서 더 낮은 숫자들로만 가서 마지막 좌표까지 갈 수 있는 경로의 갯수를 출력해야 하는 문제이다.

   처음에 본인은 단순 DFS로 답을 출력 후 제출을 했지만 시간초과가 발생했다.

   무작정 한 정점에서 4방향 모두 탐색 하도록 구현하게 되면, 최악의 경우 4^(500 x 500) 만큼의 탐색을 필요로 하기 때문에

   시간초과가 발생할 수 밖에 없다.

   따라서 본인은 DFS + DP로 구현함으로써 메모이제이션을 통해 시간을 줄여주었다.

   본인은 메모이제이션을 위해서 int DP[][] 라는 배열을 하나 선언해 주었다.

   DP[a][b] = c 의 의미는 "(a, b)에서는 (N - 1, M - 1) 까지 c개의 경로로 도달할 수 있습니다."

   를 의미한다.

   ( 위에서 (N - 1, M - 1)이라고 말한 이유는, 본인은 (0, 0)부터 (N - 1, M - 1)까지 가는 것으로 구현했기 때문이다. )

   즉, 탐색을 하다가 기존에 탐색을 한 좌표에 중복적으로 도달할 경우, 더 이상의 탐색을 필요로 없이

   DP[][] 값을 통해서 바로 경로의 갯수를 알아낼 수 있는 것이다.

  

2) 본인은 초기 DP배열의 모든 값들을 ' -1 ' 로 초기화 시켜 주었다. 0이 아닌 -1로 시켜준 이유는, 특정 좌표에서

   (N - 1, M - 1)까지 갈 수 있는 경로가 없을 경우에는 DP[][] 값에 0 이 저장될 것이다. 즉, '0'의 의미는

   "해당 좌표에서 도착점까지 갈 수 있는 경로가 0개입니다" 를 의미하고, ' -1' 의 의미는 "아직 이 좌표에서 도착점까지

   탐색을 해본적이 없으니 탐색하세요 !" 를 의미한다.

   이 둘을 구분하기 위해서 -1로 초기화 시켜 주었다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 500
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
int DP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    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;
        }
    }
}
 
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];
}
 
void Solution()
{
    Answer = DFS(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}