BOJ 1520 - 내리막길

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

 

접근

그래프 탐색에서 내리막길로만 건너가는 문제이다. 이 문제의 핵심은 어떻게 모든 경로의 수를 구하냐가 관건이다.

기존 BFS, DFS를 사용 시, 모든 경로를 탐색해야 하므로 500x500인 이번 문제에서 시간초과가 발생한다.

 

이 문제의 핵심은 Y->X와 Z->X로 갈 때, X의 경로의 수는 Y+Z 임을 이용하면 된다.

이를 메모이제이션을 통해 DP[movedX][movedY]가 0인 경우(탐색되지 않은 경우)에는 계속 앞으로 전진하고,

DP[movedX][movedY]가 0이 아닌 경우(이미 탐색된 경우)에는 DP[X] += DP[movedX][movedY]를 수행하면 된다.

 

이대로 수행하게 되면 문제가 발생한다.

이미 진행된 경로에 대해서 뒤늦게 합륙한 경로는 결과에 포함되지 않는다.

이를 해결하기 위해 우선순위 큐를 이용하여 고지가 높은 곳부터 이동하면 이 문제를 해결할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

#define MAX 9999999
#define ll long long

int n, m;
int res;
int arr[501][501];
int dp[501][501];
bool visited[501][501];
int xp[4] = {1,0,-1,0};
int yp[4] = {0,1,0,-1};

struct cmp {
    bool operator()(pair<int, pair<int,int>> a, pair<int, pair<int,int>> b) {
        return a.first < b.first;
    }
};

int func(int x, int y) {
    priority_queue<pair<int, pair<int, int>>> q;
    q.push({arr[x][y], {x,y}});
    dp[x][y] = 1;

    while(!q.empty()) {
        pair<int,int> curr = q.top().second;
        q.pop();

        for(int i=0;i<4;i++) {
            int xm = xp[i] + curr.first;
            int ym = yp[i] + curr.second;

            if(xm < 0 || ym < 0 || xm >= n || ym >= m)  continue;
            if(arr[xm][ym] >= arr[curr.first][curr.second])  continue;

            if(dp[xm][ym] == 0) {
                q.push({arr[xm][ym], {xm, ym}});
            }

            dp[xm][ym] += dp[curr.first][curr.second];
        }
    }
    return dp[n-1][m-1];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }

    res = func(0,0);
    cout << res;

    return 0;
}