[백준] 1520번 내리막 길 C++ 코드

코드

#include <iostream>
#include <cstring>

using namespace std;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,1,-1};
int n,m,a[503][503],dp[503][503];

int go(int x, int y, int height) {
    if(x == n - 1 && y == m - 1) return 1; // 도착하면 1 반환
    int &ret = dp[x][y];
    if(ret != -1) return ret; // 메모이제이션
    ret = 0; // 길이 없다면 0으로 표현해주어야함
    // 상하좌우 탐색
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= n || ny >= m || nx < 0 || ny < 0) continue;
        if(a[nx][ny] >= a[x][y]) continue;
        ret += go(nx, ny, a[nx][ny]); // 내리막길이고, 범위 안에 있다면 탐색
    }
    return ret;
}

// 내리막길로만 가므로 사이클은 안생김

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

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << go(0,0, a[0][0]) << '\n';

    return 0;
}

풀이

제일 왼쪽 위 지점에서 출발해서 오른쪽 아래 지점까지 내리막길로만 이동하는 경로의 개수를 구하는 문제이다. 각 칸에서 도착지점까지 갈 수 있는 방법의 수를 기록해놓고 조건에 맞게 탐색하면 된다. 즉, dp[a][b]는 (a,b)에서 도착지점까지 갈 수 있는 방법의 수를 의미한다.

 

이 코드에서는 끝 지점 (m-1, n-1)에 도달하면 1을 반환하여 경로가 존재한다는 것을 알리고 있다. 그런 다음, (x, y)에서 시작하여 가능한 모든 경로를 탐색하고 그 경로의 개수를 누적해 ret에 저장한다.