[BOJ 1520] 내리막 길

🔗Link

문제
풀이

💡Idea

가장 쉽게 생각할 수 있는 방법은, 가능한 길을 전부 backtracking을 해보는 방법이다.
하지만 다음과 같은 상황을 고려했을 때, 감각적으로 모든 경로를 직접 탐색해 보는 것은 어려울 것이다.

1. 지도(보드)의 크기 N과 M이 최대 500 -> 총 칸 개수는 250000 (2.5 × 10^5)
2. 꼭 최단 경로로 가지 않아도 되게 때문에, 우회 경로까지 고려해야 함.
3. 즉, 상하좌우로 4곳을 탐색할 수 있으니, 러프한 총 경로가지수는 4^(경로길이 = 250000) 따라서 우리는 다른 방식으로 접근해야 한다.

더 낮은 칸으로만 갈 수 있단 조건을 이용해, 그 칸에 도달할 수 있는 경로의 수를 dp로 저장해두면 된다.
현재 칸까지 도달하는 방법은, 그 칸보다 더 높은 칸에서만 도달 할 수 있기 때문에, 그 더 높은 칸들까지 도달하는 방법의 수의 합이다.

지	도
50	45	37	32	30
35	50	40	20	25
30	30	25	17	28
27	24	22	15	10

경	로	가	지	수
1	1	1	1	1
1	0	0	2	1
1	0	0	2	0
1	1	1	3	3

🔑Code

#include <bits/stdc++.h>
using namespace std;

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

int N, M;
int board[500][500];
int dp[500][500];
priority_queue<tuple<int,int,int>> pq;


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

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

    pq.emplace(board[0][0], 0, 0);
    dp[0][0] = 1;

    while(!pq.empty()){
        auto [curH, curX, curY] = pq.top(); pq.pop();
        
        for(int i = 0; i < 4; i++){
            int nx = curX + dx[i];
            int ny = curY + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(board[nx][ny] >= curH) continue;
            if(dp[nx][ny] == 0)  // 각 칸당 한번만 pq에 들어가도록 조건 설정
                pq.emplace(board[nx][ny], nx, ny);
            dp[nx][ny] += dp[curX][curY];
        }
    }

    cout << dp[N-1][M-1] << '\n';

    return 0;
}

🗨️ Side Notes

어느덧 10월이 됐습니다. 이번 달도 파이팅 합시다!