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

www.acmicpc.net/problem/1520

1520번: 내리막 길

DFS + DP 문제 유형

1949번 문제와 비슷한 유형입니다. (트리 구조인 것을 제외하면) DFS만을 이용해 (0,0)부터 (m-1,n-1) 까지 갈 수 있는 경우의 수를 구하면 최대 4방향에 500x500의 시간복잡도 때문에 시간초과가 발생할 수 있습니다. 따라서 메모제이션을 사용하여 시간복잡도를 줄여야합니다. 먼저 DFS를 통해 도착점에 도달하면 1을 리턴하고, 다시 위로 올라가며 탐색을 시작하는데, 이때 이미 방문했던 곳을 가면 이전에 경로의 값을 모두 더해주는 방식입니다. 즉 Top-Down으로 쪼개졌다가, Bottom-Up으로 경로의 값을 더해가는 구조입니다.

 

#include <iostream>
#include <cstring>
using namespace std;

int m, n;
int map[501][501];
int dp[501][501];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int DFS(int x, int y) {
    if(x == m - 1 && y == n - 1) return 1; // 도착점에 도달
    if(dp[x][y] != -1) return dp[x][y]; // 이미 방문했으면 저장된 값 리턴
    dp[x][y] = 0; // 도착점에 도달 못하면 0을 리턴
    
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >= 0 && nx < m && ny >= 0 && ny < n) {
            if(map[x][y] > map[nx][ny]) {
				dp[x][y] += DFS(nx, ny);
			}
        } 
    }
    
    return dp[x][y];
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>m>>n;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            cin>>map[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp)); // -1로 초기화 (아직 방문하지 않음)
    cout<<DFS(0, 0);
}