BOJ : 1520 내리막 길

 

---

[BOJ 1520(G4) 리뷰]

언뜻보면 그냥 BFS,DFS문제로 보이지만 DP를 이용하여 풀지 않으면 시간초과가 난다.

따라서 목적지 까지 갔던 경로를 기억해야 하고 지금 가고있는 경로가 이미 목적지에 도착했던 경로라면 굳이 목적지 까지 갈필요가 없다. 이를 DP배열을 통해 구현했다.

 

목적지에 도착했을때에만 1을 반환하도록 하면 결국 DP[1][1]에는 목적지 까지 도착한 경로의 갯수만이 저장될것이다.

 

---

#include <bits/stdc++.h>
using namespace std;
int N, M;
int board[501][501];
int dp[501][501];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

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

    dp[r][c] = 0;
    for (int dir = 0; dir < 4; dir++)
    {
        int nr = r + dx[dir];
        int nc = c + dy[dir];
        if (nr <1 || nr>N || nc < 1 || nc > M) continue;
        if (board[nr][nc] >= board[r][c]) continue;
        dp[r][c] += dfs(nr, nc);
    }

    return dp[r][c];
}



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

    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
            cin >> board[i][j];
    }
    
    for (int i = 1; i <= N; i++)
    {
        fill(dp[i], dp[i] + M + 1, -1);
    }

    cout << dfs(1, 1);

}