[백준/C,C++] 1520번: 내리막 길

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

1520번: 내리막 길

풀이

해당 문제를 보고 DFS, BFS문제구나 생각을 했습니다.

 

관건은 동적계획법을 사용해 어떻게 연산 수를 줄이는 것인가인데

 

다른 고수분들의 풀이를 보고 참고해 풀었습니다.

 

DP[y][x] = 현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수로 가정하고

 

이를 사용한다면 탐색의 횟수를 줄일 수 있습니다.

 

 

예제를 통해 적용해보겠습니다.

 

 

최초 출발 지점인 50에서 10으로 갈 수 있는 경로의 개수는

 

35 그리고 45에서 갈 수 있는 경로의 개수를 합친 것과 같습니다.

 

35에서는 갈 수 있는 경로의 개수가 1개, 45에서는 2개이므로 50에서 10으로 갈 수 있는 경로의 개수는 3개 인 것이죠.

 

 

결과적으로 DP 배열은 위와 같이 채워진다고 보시면 됩니다.

 

첫 번째 경로를 살펴보죠.

 

목적지에 도달한 경우는 기저 사례이고 1을 반환합니다.

 

그리고 50에서부터 지나온 DP[y][x]에는 하나의 경로가 존재하게 됩니다.

 

 

두 번째 경로는 기저 사례에 도달하기 전 4, 4 좌표인 15를 만나 1을 반환받게 됩니다.

 

1,4 좌표인 32에서는 하나의 경로가 더 존재하는데 이 역시 2, 4 좌표인 20을 만나 1을 반환받고

 

32에는 2가지 경로가 존재함을 알 수 있습니다.

 

즉 DP[y][x]는 y, x 좌표에서 갈 수 있는 좌표들이 가진 경로의 개수 합이라고 보면 됩니다.

 

DP[1][1]은 DP[2][1] + DP[1][2]일 것이고, DP[1][4]는 DP[2][4] + DP[1][5]일테죠.

 

 

이 과정에서 목표지점으로 갈 수 있는 경로의 개수가 확인된 좌표에서는 더 이상 탐색하지 않고

 

해당 지점의 경로 개수를 반환하게 되면서 연산의 수가 매우 줄어들게 됩니다.

 

#include <iostream>
#include <cstring>

using namespace std;

const int MAX = 501;
const pair<int, int> direction[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

int M, N;
int map[MAX][MAX];
int cache[MAX][MAX];

int DFS(int y, int x)
{
    // 기저 사례 (목적지에 도달)
    if (y == M && x == N) {
        return 1;
    }

    // 방문하지 않은 지점이라면 계속 탐색
    if (cache[y][x] == -1) {
        cache[y][x] = 0;
        for (int i = 0; i < 4; i++) {
            int ny = y + direction[i].first;
            int nx = x + direction[i].second;
            if (map[ny][nx] != 0 && map[y][x] > map[ny][nx]) {
                cache[y][x] += DFS(ny, nx);
            }
        }
    }

    // 방문한 곳이라면 해당 좌표에서 목적지까지 도달할 수 있는 경로의 개수 반환
    return cache[y][x];
}

int main(void)
{
    cin >> M >> N;

    memset(cache, -1, sizeof(cache));
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }

    cout << DFS(1, 1);

    return 0;
}

반례

Input

5 5
10000 9142 2314 9554 9000
8777 5654 1324 2344 7566
7654 4300 1100 1580 6543
4800 3999 2999 1999 2000
9999 300 456 991 44

Output

4