818. Race Car

이 문제는 DP로 쓰거나 BFS로 쓸 수 있습니다.BFS의 사고방식은 시작 상태에서 출발하여 층을 나누어 target에 달하는 걸음수를 찾는 것이다.이곳의 상태는 두 점으로 구성되어 위치와 속도다.
제가 먼저 level Order BFS의 해법을 썼는데 답안인 DP와 BFS2의 해법을 자세히 보고 싶지 않아요. 이 문제는 너무 어려워요.

class Solution {
    public int racecar(int target) {
        Map> map = new HashMap<>();
        map.putIfAbsent(0, new HashSet());
        map.get(0).add(1);
        Queue queue = new LinkedList<>();
        queue.offer(new State(0, 1));
        int level = 0;
        if (target == 0) return 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                State st = queue.poll();
                if (st.pos > target * 2 || st.pos < target * -1) continue;
                //A
                int nextPos = st.pos + st.speed;
                
                int nextSpeed = st.speed * 2;
                map.putIfAbsent(nextPos, new HashSet<>());
                if (map.get(nextPos).contains(nextSpeed)) continue;
                if (nextPos == target) return level + 1;
                map.get(nextPos).add(nextSpeed);
                queue.offer(new State(nextPos, nextSpeed));
                //R
                nextPos = st.pos;
                nextSpeed = st.speed > 0 ? -1 : 1;
                if (map.get(nextPos).contains(nextSpeed)) continue;
                map.get(nextPos).add(nextSpeed);
                queue.offer(new State(nextPos, nextSpeed));
            }
            level++;
        }
        return -1;
    }
    
}
class State {
    int pos;
    int speed;
    
    public State(int pos, int speed) {
        this.pos = pos;
        this.speed = speed;
    }
}