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

문제링크 : https://www.acmicpc.net/problem/17391

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M;
int arr[301][301];
bool visited[301][301];

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

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

    while(!q.empty())
    {
        auto [y, x, cnt] = q.front();
        q.pop(); 

        if(y == N-1 && x == M-1)
        {
            cout << cnt;
            return;
        }

        for(int i=0; i<2; i++)
        {
            for(int j=1; j<=arr[y][x]; j++) //부스터 만큼 이동
            {
                int ny = y + dy[i]*j;
                int nx = x + dx[i]*j;

                if(nx < 0 || ny < 0 || ny >= N || nx >= M || visited[ny][nx]) continue;
                visited[ny][nx] = 1;
                q.push({ny, nx, cnt+1});
            }
        }
    }
}

int main()
{
    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 >> arr[i][j];
        }
    }

    bfs();

    return 0;
}

 

어렵지 않은 bfs 문제이다.

 

최소 거리 1 ~ 최대 거리 부스터 수치 만큼 값을 이동시키며 카운팅을 해나가면 된다.

가장 빨리 목적지에 도착한 경우의 cnt를 출력하면 목표값이 된다.

cnt 값도 해당 좌표값과 같이 증가시켜주기 위해 que에 다음 좌표값 뿐만이 아니라 cnt 값도 같이 1 증가하여 넘겨준다.