[アルゴリズム解解析]BOJ 1520下り坂

新しく出た問題はBOJ 1520下り坂題~!

BOJ 1520下り坂

旅行に行った勢俊は地図を手に入れた.この地図は下図のように矩形で、複数の格子に分かれています.1つの格子は1つの場所を表し、各格子にはその場所の高さが書かれており、各場所間の移動は地図上の上下左右に隣接する場所間でしか行われない.

今一番左上のチェックが表示されているところの勢俊は、一番右下のチェックが表示されているところに行きます.しかし、私はできるだけ力を入れないで、いつも高さのもっと低いところに移動して、目標の場所まで移動したいと思っています.上記の地図には、次の3つの方法があります.
地図に示すように、最左上から最右下にかけて常に下り坂にしか移動しない経路数を求めるプログラムを作成します.

にゅうしゅつりょく

私の答え

問題を見ると、BFSで解決しようと思います.
普段はDFSアルゴリズムを考えていますが、BFSはDFSに比べてイマイチで思い出せないのでBFS、DFSになるかもしれませんが、DFSタイムアウトも心配してBFSで練習してみました.
与えられた例の入力を手で確認したところ、ループや重複検査経路数は発生しなかったが、각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만とはっきり書いてあるので、他のテストケースでは間違いないと思う.
しかしアクセス配列を書くと、1つのポイントが2つのルートでアクセスできるため、これは利用できないようですが、どうやってアクセスするのでしょうか...?やりながら悩んだ
そしてDPを使えば良いというヒントが得られ、DPを使って2次元ベクトルDPを各点に保存する可能な累積パス数を、最終的にdp[M-1][N-1]の値に戻せば良いので、コードを作成して提出したが、まだタイムアウトの問題は解決していない!
同じ質問に答えた友人のヒントを見ると、BFSを適用する際に、通常のキューではなく優先キューを使用していることがわかりました.高い位置からアクセスしなければ、各位置で探索できません.
図から見ると、

20と書いてある[1,3]ポイントには2つの到着方法があります!
上32から直接降りる方法と32-30-25から戻る2つの道があります.
各ポイントで4つのポイントをナビゲートし、値の小さいポイントをキューに入れるだけで、

32から20の場合、dp配列は右側と同じになります.

以降32−30−25−20ルートの探索を行うと、探索済みの20のdp値が再記録され、それに応じて、以降探索した17のdp値も更新される.
この過程でタイムアウトが発生したと思いますが、これを防ぐために優先順位キューを使用して、まず高さの高いセルをチェックします!
また、20において2番目の値を増やし、20のdp値をdp[1][3]から2に変更した場合には、[1,3]キューに入る必要はない(既にキューに入っている)ため、dp値が0より大きいと優先キューに入れるプロセスは省略される.

コード#コード#

#include <iostream>
#include <vector>
#include <queue>

// BOJ 1520 내리막길, BFS
using namespace std;

// 각 지점의 높이 값과 해당 좌표 값을 함께 저장, 구조체 사용
typedef struct point {
    int height;
    pair<int, int> coor;

    point() {
        height = 0;
    };

    point(int h, pair<int, int> c){
        height = h;
        coor = c;
    }

} Point;

// 우선순위 큐 정렬 기준, 높이가 높은 순서대로 
struct comp {
    bool operator()(Point a, Point b){
        return a.height < b.height;
    }
};

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

int getPathToExit(int M, int N, vector<vector<int>> map){
    vector<vector<int>> dp(M, vector<int>(N,0));  // 경로 수 기록
    pair<int, int> destination = make_pair(M-1, N-1);  // 목적지
    priority_queue<Point, vector<Point>, comp> pq;

    queue<pair<int, int>> points; // 탐색할 좌표들

    pair<int, int> location;  // 현재 확인하고 있는 위치

    pq.push(Point (map[0][0],make_pair(0,0)));
    dp[0][0] = 1;

    while (!pq.empty()){
        location = pq.top().coor;
        pq.pop();

        if (location == destination){
            continue;
        }

        int height = map[location.first][location.second];

        for (int i = 0; i < 4; ++i) {  // 위쪽 칸부터 시계 방향으로 확인
            int row = location.first + dy[i];
            int col = location.second + dx[i];

            if (row >= 0 && row < M && col >= 0 && col < N){
                if (map[row][col] < height){
                    if (dp[row][col] == 0){  // 처음 dp값을 확인하게 될 때에만 pq.push
                        pq.push(Point(map[row][col], make_pair(row,col)));
                    }
                    dp[row][col] += dp[location.first][location.second];
                }
            }
        }
    }


    return dp[M-1][N-1];
}

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

    vector<vector<int>> map(M, vector<int>(N, 0));
    for (int i = 0; i < M; ++i) {
        for (int j=0; j<N; j++){
            cin>>map[i][j];
        }
    }

    int answer = getPathToExit(M, N, map);

    cout<<answer;

    return 0;
}

和弦が少し長く感じましたが、少し不安でしたが、とにかく、草は完成していました!