1520 내리막 길

1520. 내리막 길 / c++ / Gold3 / 36분

문제

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

1. M X N 의 지도에 각 칸마다 높이가 주어진다.
2. 상하좌우의 낮은 칸으로만 이동이 가능할 때
3. 0,0에서 M-1,N-1까지의 경로의 수를 출력하라

접근 방식

동적 프로그래밍

1. 처음엔 BFS로 풀었다. (시간초과)
2. DP라는걸 생각하고 보니,
   1. dp[i]는 상하좌우 dp의 합이었다.
   2. dp[0][0]을 1로 지정해주면, dp[M-1][N-1]에 경로의 수가 저장되었다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
using namespace std;

int M, N;
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { -1, 1, 0, 0 };
int board[500][500] = {};
int dp[500][500] = {};

int DP(pair<int,int> pos)
{
    if (dp[pos.first][pos.second] == -1)
    {
        dp[pos.first][pos.second] = 0;
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> nextPos;
            nextPos.first = pos.first + dy[i];
            nextPos.second = pos.second + dx[i];

            if (nextPos.first < 0 || nextPos.first >= M || nextPos.second < 0 || nextPos.second >= N) continue;
            if (board[nextPos.first][nextPos.second] <= board[pos.first][pos.second]) continue;

            dp[pos.first][pos.second] += DP(nextPos);
        }
    }

    return dp[pos.first][pos.second];
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> M >> N;
    fill(&dp[0][0], &dp[M][N - 1], -1);

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

    dp[0][0] = 1;

    cout << DP({ M - 1, N - 1 }) << '\n';

    return 0;
}

다시 생각해 볼 점

1. DP는 하위 문제의 반복작업을 줄여준다. (대신 저장공간 때문에 메모리가 증가)
2. BFS도 DP로 풀 수 있다는 것을 깨달았다.