Jump Game IV

정수형 벡터 arr을 받고,

0번째 인덱스에서 시작하여 마지막 인덱스까지 가는데 최소 점프 수를 구하는 문제.

점프는 세 가지 방법이 있다.

인덱스 + 1이 벡터의 길이보다 작다면 한칸 앞으로 점프할 수 있다.

인덱스 - 1이 0보다 크거나 같다면 한칸 뒤로 점프할 수 있다.

arr[인덱스]의 숫자와 같은 숫자가 있는 인덱스로 점프할 수 있다.

class Solution {
public:
    int minJumps(vector<int>& arr) {

        int length = arr.size();
        if (length == 1)
        {
            return 0;
        }
        
        map<int, vector<int>> hash{};

        for (int i = 0; i < length; ++i)
        {
            hash[arr[i]].push_back(i);
        }

        queue<int> waitings{};
        waitings.push(0);
        vector<bool> visited(length, false);
        visited[0] = true;
        
        int target{length - 1};
        int result{0};
        while (waitings.empty() == false)
        {
            int localLength = waitings.size();
            for (int i = 0; i < localLength; ++i)
            {
                int index{waitings.front()};
                waitings.pop();

                for (auto& next : hash[arr[index]])
                {
                    if (visited[next])
                    {
                        continue;
                    }

                    if (next == target)
                    {
                        return result + 1;
                    }

                    visited[next] = true;
                    waitings.push(next);
                }
                
                hash[arr[index]].clear();

                if (index + 1 < length)
                {
                    if (index + 1 == target)
                    {
                        return result + 1;
                    }

                    if (visited[index + 1] == false)
                    {
                        visited[index + 1] = true;
                        waitings.push(index + 1);
                    }
                }

                if (0 < index && visited[index - 1] == false)
                {
                    visited[index - 1] = true;
                    waitings.push(index - 1);
                }
            }

            ++result;
        }

        return result;
    }
};