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

백준의 무한부스터(17391) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 출발점에서 도착점까지 가는데 아이템을 획득하게 되는 최소 갯수를 출력해야 하는 문제인데, 모든 좌표에

   아이템이 존재하기 때문에 사실상 최단경로를 묻는 문제인 것 같았다...

   본인은 이 문제를 단순 BFS로 탐색을 진행해 주었다.

   Queue에서는 [ x좌표 , y좌표 , 주운 아이템의 갯수 ] 를 관리해 주었다.

 

[ 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 300
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 1 };
int dy[] = { 1, 0 };
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(0, 0), 0));
    Visit[0][0] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == N - 1 && y == M - 1)
        {
            cout << Cnt << endl;
            return;
        }
        
        for (int i = 0; i < 2; i++)
        {
            for (int k = 1; k <= MAP[x][y]; k++)
            {
                int nx = x + dx[i] * k;
                int ny = y + dy[i] * k;
 
                if (nx >= 0 && ny >= 0 && nx < N && ny < M)
                {
                    if (Visit[nx][ny] == false)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                    }
                }
            }
        }
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}