[boj] 백준 1520 내리막 길 (c++) - dfs, dp

[문제]

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

1520번: 내리막 길

 

[풀이]

문제 자체는 완전 탐색으로 dfs를 이용하면 된다. 하지만 이 경우 4^(500*500)만큼의 탐색을 요구할 수 있기 때문에 시간 초과가 발생한다. 따라서 dp를 이용한 메모이제이션을 통해 탐색 시간을 단축하도록 하는 것이 핵심이다.

 

dp[i][j] = c 는 i, j 좌표에서 n-1, m-1 좌표까지 이동할 수 있는 경우의 수를 나타낸다.

좌표 끝에 도달하면 도달 가능한 경우가 1가지 추가되는 것이므로 1를 return하고 이는 dp[r][c] += dfs(nr, nc) 식을 통해 지나온 모든 경로에 저장된다. 

처음 dp를 -1로 초기화하고 -1이 아닌 경우, 해당 칸에 도착했을 때 좌표 끝에 도달 가능한 경우의 수를 이미 알고 있다는 뜻이므로(메모이제이션) dp[r][c]를 return 해준다. 

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n, m;
int board[501][501];
int dp[501][501];
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int dfs(int r, int c) {
    if (r == n - 1 && c == m - 1) return 1;
    if (dp[r][c] != -1) return dp[r][c];

    dp[r][c] = 0;
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];

        if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
        if (board[nr][nc] < board[r][c]) {
            dp[r][c] += dfs(nr, nc);
        }
    }

    return dp[r][c];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0);

}