[C++]백준 17391번 무한부스터

📌문제 링크

---

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

📌문제 설명

---

bfs로 해결이 가능한 오른쪽, 아래로 이동하는 최적 경로 찾기이다. dp배열을 만든 후 부스터로 움직일 수 있는 모든 경우의 수중 최소값을 갱신하는 경우를 탐색한다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int mp[301][301], dp[301][301], N, M;

struct comp{
    int x, y, boostCnt, cnt;
};

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

void bfs(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            dp[i][j] = INT_MAX;
        }
    }
    queue<comp> q;
    q.push({0, 0, mp[0][0], 0});
    dp[0][0] = 0;
    while(!q.empty()){
        auto [x, y, boostCnt, cnt] = q.front();
        q.pop();
        if(x == N - 1 && y == M - 1){
            continue;
        }
        for(int i = 1; i <= boostCnt; i++){
            if(x + i < N && dp[x + i][y] > cnt + 1){
                dp[x + i][y] = cnt + 1;
                q.push({x + i, y, mp[x + i][y], cnt + 1});
            }
            if(y + i < M && dp[x][y + i] > cnt + 1){
                dp[x][y + i] = cnt + 1;
                q.push({x, y + i, mp[x][y + i], cnt + 1});
            }
        }
    }
    cout << dp[N - 1][M - 1];
}

void solve(){
    input();
    bfs();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}