점프 점프 - 11060번 백준

문제

문제 난이도 : 실버 2

문제 분류 : BFS (DP)

 

문제 풀이

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
    //Input
    int n = 0;
    vector<short> Map;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        short Tmp;
        cin >> Tmp;
        Map.push_back(Tmp);
    }
    vector<bool> Visited(Map.size(), false);
    queue<pair<short,short>> q;
    q.push({ 0, 0 });
    short MinVal = 10000;

    while (!q.empty())
    {
        
        pair<short, short> p = q.front();
        q.pop();
        if (Visited[p.first]) continue;
        Visited[p.first] = true;
        if (p.second > MinVal) continue;
        if (p.first == Map.size() - 1)
        {
            MinVal = min(p.second, MinVal);
        }

        vector<short> ToGo;
        for (int i = 1; i <= Map[p.first]; ++i)
        {
            if (i + p.first < Map.size())
            {
                if (!Visited[i + p.first]) 
                {
                    ToGo.push_back(i + p.first);
                }
                
            }
        }
        for (int i : ToGo)
        {
            q.push({ i ,p.second + 1 });
        }

    }

    if (MinVal == 10000)
    {
        cout << -1;
    }
    else
    {
        cout << MinVal;
    }
}