[BOJ 백준] 1520번 내리막 길

문제

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

1520번: 내리막 길

접근

 내리막 길로만 갔을 때 도착지까지 갈 수 있는 경로의 갯수를 구하는 문제이다. 이는 DFS로만 풀면 시간 초과가 나기 때문에 DP + DFS를 이용하여 문제를 해결하였다. 

코드

#include <iostream>

using namespace std;

int m, n, map[505][505], visit[505][505], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};

int dfs(int a, int b) {
    if (a == m - 1 && b == n - 1)
        return 1;
    else if (visit[a][b] == -1) {
        visit[a][b] = 0;
        for (int i = 0; i < 4; i++) {
            int newx = a + dx[i];
            int newy = b + dy[i];
            if (newx >= 0 && newx < m && newy >= 0 && newy < n && map[newx][newy] < map[a][b])
                visit[a][b] += dfs(newx, newy);
        }
    }
    return visit[a][b];
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            visit[i][j] = -1;
        }
    }
    cout << dfs(0, 0);
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study