1520번 : 내리막 길(C++, 시간 초과, Bottom-up, Top-down)

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

1520번: 내리막 길

 

이번 문제는, 다이나믹 프로그래밍 문제이다.

대학생 때, Bottom-up 접근 방법, Top-down 접근 방법들을 배웠던 기억이 난다. 그러면서 호출되는 순서를 그래프로 표현해봐라는 과제가 있었는데, 하면서도 이걸 왜하나 싶었는데...

 

 

 

이제 그 중요성을 알 수 있었다.

 

 

 

또한, 지금까지 접근했던 문제들이 Bottom-up으로 모두 풀리던 문제들이여서, 이 문제를 만났을 때 접근 방식조차 생각해지 못했다 ㅠㅠ

 

 

 

---

 

 

 처음에 이 문제를 풀기 위해서, DFS 접근을 생각하고 모든 칸을 방문하며, 조건이 만족하면 1을 더해주도록 했다. 정답은 나오지만, 시간초과가 발생한다.

 

 

 

 

시간 초과가 발생하는 이유는, DFS는 Return하면서 방문했던 노드를 재 방문할 수 있다.

 

 

 

 

이 말이 무슨 말이냐면, 

 

 

 

 

 

이 그림을 보면, 20은 재방문이 된다. 만약에 20처럼 재방문이 되는 칸이 많아진다면 시간초과가 무조건 발생할 수 있다.

 

 

 

 

50,45,37,32에 대해서는 재방문되지 않는다.

 

 

 

 

M = 4, N = 5인 경우에 그래프를 그려보자.

 

 

 

 

 

위와 같은 그래프를 그려질 수 있다. 좌측에서부터 상, 하, 좌, 우이다. 5,5와 4,6은 범위를 초과하므로 제외해야 한다. 또한, 내리막길의 조건에 부합하는 것만 경로의 수로 더해질 수 있다.

 

 

 

 

함수를 정의할 때, 매개변수로 행과 열의 정보가 담을 수 있으면 된다.

 

 

 

 

DP를 이용한 재귀함수에서 정의해줘야 할 조건은 다음과 같다.

 

 

1. 종료 조건

2. 방문 확인(메모이제이션)

3. 호출 조건

 

 

 

위의 세가지를 완성해서 함수를 작성하면 된다.

 

 

 

 

여기서 Bottom-Up을 사용하지 않는 이유에 대해서 좀 적어보겠다.

 

 

 

DP[i][j]를 구하기 위해선, DP[i - 1][j], DP[i + 1][j], DP[i][j - 1], DP[i][j + 1]의 합을 구해야 한다. 일반적으로 우측 아래방향으로 배열을 읽는다면, DP[i + 1][j]와 DP[i][j + 1]의 값을 구하기 어렵다.

 

 

 

 

하향식 접근이 더 적합하다!

 

 

 

---

 

 

해설코드(C++).

#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int map[501][501] = { 0 };
int dp[501][501] = { 0 };
int N, M;
int op[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
 
int dfs(int i, int j) {
    if (i == 1 && j == 1)
        return 1;
 
    if (dp[i][j] != -1)
        return dp[i][j];
 
    dp[i][j] = 0;
    for (int o = 0; o < 4; o++) {
        int n_i = i + op[o][0];
        int n_j = j + op[o][1];
        if (n_i >= 1 && n_i <= M && n_j >= 1 && n_j <= N && map[n_i][n_j] > map[i][j])
            dp[i][j] += dfs(n_i, n_j);
    }
 
    return dp[i][j];
}
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> M >> N;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
 
    cout << dfs(M, N) << endl;
    return 0;
}