[백준/c++] BOJ 17391 - 무한부스터

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

17391번: 무한부스터

 

문제 설명

NxM 직사각형 모양의 맵 안에서 게임이 진행된다. 모든 격자 안에는 특정 개수의 부스터 아이템이 존재한다. 출발 지점은 1행 1열에 위치하며, 도착 지점은 N행 M열이다. 카트바디가 격자에 멈추어 있을 때, 격자에 놓여 있는 부스터 아이템을 전부 습득한다. 부스터를 x개 습득했다면 한 방향을 정해 오른쪽으로 최대 x칸 가거나, 아래쪽으로 최대 x칸을 이동할 수 있다. 이동 후 멈추면서 보유하고 있던 부스터 아이템은 모두 소진된다. 최소한의 이동으로 목표 지점에 도달한다.

N, M (1 <= N, M <= 300)

해결

단순한 bfs문제이다. 다른 bfs문제들과 다른 점은 아래, 오른쪽 방향으로만 이동할 수 있다는 것과 최대 부스터의 개수만큼 이동할 수 있다는 것이다. 부스터의 개수가 3개라면 1, 2, 3칸을 이동할 수 있다. 따라서 부스터의 개수만큼 반복문을 돌려 주어야 한다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
int board[301][301];
int visited[301][301];
int dx[2] = { 0, 1 }, dy[2] = { 1, 0 };

int range_over(int nx, int ny) {
    return nx < 0 || ny < 0 || nx >= n || ny >= m;
}

void bfs() {
    queue<pair<pair<int, int>, int>> q;
    q.push({ { 0, 0 }, 0 });
    visited[0][0] = 1;

    while (!q.empty()) {
        auto cur = q.front(); q.pop();
        for (int dir = 0; dir < 2; dir++) {
            for (int i = 1; i <= board[cur.x.x][cur.x.y]; i++) {
                int nx = dx[dir] * i + cur.x.x, ny = dy[dir] * i + cur.x.y;
                if (range_over(nx, ny) || visited[nx][ny]) continue;
                if (nx == n - 1 && ny == m - 1) {
                    cout << cur.y + 1;
                    return;
                }
                visited[nx][ny] = 1;
                q.push({ {nx, ny}, cur.y + 1 });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cin >> board[i][j];
    }

    bfs();
}