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

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

 

지도가 주어졌고 끝 지점까지 탐색하는 문제이기에 DFS를 사용해야 됨을 인지했습니다.

 

다 탐색할경우 4^(500 * 500)이였기에 시간복잡도를 줄일 방법이 필요했고, 그에 따라 DP를 사용해야 되는 것까지는 인지를 했는데 어떤 식으로 접근할 지 고민이 됐습니다.

 

 

처음 접근은 'dp 배열의 값 =  이 지점까지 올 수 있는 경로의 개수'로 지정했습니다.

dp[m][n]에 정답이 나오도록 한 것이죠.

 

하지만 DFS를 통해 끝지점에 도착한 뒤, 재귀를 통해 이전 배열의 값을 하나씩 구해가야 하는데,

마지막 점에 도착했을 때 리턴 값을 뭐로 해야할 지가 참 난감했습니다.

 

마지막 값에서 이전 방향의 값들을 모두 더한다?

근데 그럼 거기서 또 dfs를 해야하나???

이런 식으로 미궁에 빠진 것이죠.

 

 

 

재귀의 리턴 순서와 반대되는 방향으로 값을 채우려 했기에 생긴 문제였습니다.

재귀를 호출하면서 채웠으면 모를까 아니었기에 접근 방식을 바꿔야 했습니다.

 

 

 

고수분들의 풀이를 보고 제가 dp 배열의 값 설정을 잘못 접근했다는 걸 깨달았습니다.

'dp 배열의 값 =  현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수'

으로 설정하자 모든 게 명쾌해졌습니다.

 

마지막 지점에 도착하면 1을 리턴하고

리턴됨에 따라 각 지점에 그 값을 더하는 방식으로 말이죠.

if(y == height && x == width){
        return 1;
    }

dp[y][x] += dfs(ny, nx);

 

 

이때 주의해야 할 점은 dp 배열의 값을 초기에 미리 세팅해야 된다는 점입니다!

탐색하지 않은 지점은 -1로 세팅해둬야

탐색한 지점을 0 이상이라고 가정할 수 있고, 그래야만 경우의 수를 줄일 수 있습니다!!

이미 탐색한 지점은 계산하지 않고 배열의 값을 이용하는 메모이제이션을 활용하는 겁니다.

for(int i = 1; i <= height; i++){
        for(int j = 1; j <= width; j++){
            cin>>map[i][j];
            dp[i][j] = -1;
        }
    }

 

// 방문하지 않은 지점일 때
    if(dp[y][x] == -1){
        dp[y][x] = 0;

// 방문해본 지점이라면 이 좌표에서 목적지까지의 경로 개수 반환
    return dp[y][x];

 

 

 

예제를 통해 보여드리겠습니다.

이런 식으로 예제는 총 3가지 경우의 수가 나옵니다.

 

50에서 10으로 가는 경우의 수는

(1) 35로 가는 방향과 (2) 45로 가는 방향의 경우의 수를 더하면 나옵니다.

 

(1) 먼저 35로 가는 방향을 보면 10을 만날때까지 dfs를 하다가

10에 도달하여 1을 리턴하고, 그에 따라 배열의 값이 쭉쭉 채워집니다.

 

(2) 그 다음 45로 가는 방향을 보면 15라는 숫자에서 배열의 값이 이미 1로 채워져있습니다.

그렇기에 끝까지 탐색하지 않고 배열의 값인 1을 리턴한 뒤, 이전 배열의 값들을 채웁니다.

 

45로 가는 방향은 30을 통해 가는 경로도 존재하는 데

이 경로는 20에서 이미 배열이 채워져 있기에 20의 배열의 값을 리턴해주고,

32에서 그 값이 더해집니다.

 

 

dp 배열의 값에 대해 알아보면 결국 아래와 같은 식으로 되는 겁니다.

'dp 배열의 값 =  현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수'

가 잘 반영된 모습을 볼 수 있습니다!!

 

 

전체 코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int map[505][505];
int dp[505][505];
int width, height;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};

int dfs(int y, int x){
    if(y == height && x == width){
        return 1;
    }

    // 방문하지 않은 지점일 때
    if(dp[y][x] == -1){
        dp[y][x] = 0;
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny >= 1 && ny <= height && nx >= 1 && nx <= width){
                if(map[ny][nx] < map[y][x]){
                    dp[y][x] += dfs(ny, nx);
                }
            }
        }
    }
    
    // 방문해본 지점이라면 이 좌표에서 목적지까지의 경로 개수 반환
    return dp[y][x];
}

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

    cin>>height>>width;
    for(int i = 1; i <= height; i++){
        for(int j = 1; j <= width; j++){
            cin>>map[i][j];
            dp[i][j] = -1;
        }
    }

    int ans = dfs(1, 1);
    cout<<ans;
    return 0;
}

 

 

dp 배열 값을 무엇으로 설정하는 지가 얼마나 중요한 지 알 수 있는 문제였습니다!