[Algorithm/C++17] 백준 1520 내리막 길

문제

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

1520번: 내리막 길

풀이 방법

항상 낮은 칸으로 이동하며 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 갈 수 있는 경로의 개수를 구하는 문제다.

처음엔 단순한 탐색문제인 줄 알고 모든 케이스를 다 탐색해서 개수를 구하려고 했다. 하지만 최악의 경우를 생각해본다면 한 정점에서 4방향으로 모든 정점을 계속해서 탐색할 수도 있기 때문에 다른 방법이 필요하다.

 

좀 더 생각해보면, 어떤 점(y, x)에서 제일 오른쪽 아래 지점까지가는 경로의 개수를 n개라고 했을 때,

상하좌우 정점은 (y - 1, x) = (y + 1, x) =  (y, x - 1) = (y, x+ 1) = n-1 이라는 것을 알 수 있다.

따라서 DP를 곁들여 탐색을 최소화하면 제한 시간 내 풀이가 가능하다.

코드

#include <cstdio>
#include <vector>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int solve(vector<vector<int>>& v, vector<vector<int>>& dp, int y, int x)
{
    int M = v.size();
    int N = v[0].size();
    // 이미 계산된 정점일 경우 그대로 반환
    if(dp[y][x] != -1) return dp[y][x];
    // 기저 케이스
    if(y==M-1 && x==N-1) return 1;
    
    // 처음 방문한 정점일 때 상하좌우 탐색
    dp[y][x] = 0;
    for(int i=0; i<4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >=M || nx < 0 || nx >= N) continue;
        if(v[ny][nx] >= v[y][x]) continue;
        // 낮은 칸 일 경우 경로의 개수를 계속해서 더한다.
        // 기저 케이스부터 차근차근 더해져 dp[y][x]에는 (y, x)에서 (M-1, N-1)까지 경로의 개수가 저장된다.
        dp[y][x] += solve(v, dp, ny, nx);
    }
    return dp[y][x];
}
int main()
{
    int M, N;
    scanf("%d %d", &M, &N);
    vector<vector<int>> v(M, vector<int>(N));
    for(int i=0; i<M; i++)
    {
        for(int j=0; j<N; j++)
        {
            scanf("%d", &v[i][j]);
        }
    }
    
    vector<vector<int>> dp(M, vector<int>(N, -1));
    int answer = solve(v, dp, 0, 0);
    printf("%d", answer);
    
    return 0;
}

고찰

생각까진 할만했는데 구현에 들어가니 조금 어려웠던 문제. DP의 감을 아직 못 잡은 느낌이다.