Minimum Jumps to Reach Home

1654. Minimum Jumps to Reach Home

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        if (x == 0) {
            return 0;
        } else if (x == a) {
            return 1;
        }
        vector<int> map(6000, 0);
        map[0] = -1;
        map[a] = 1;
        for (auto f: forbidden) {
            map[f] = -1;
        }
        queue<int> q;
        q.push(a);
        while (!q.empty()) {
            int qv = q.front();
            q.pop();
            int pos = qv;
            if (pos < 0) {
                pos = -pos;
            }
            if (map[pos] != -1) {
                int pp = pos - b;
                if (0 < pp && 0 < qv && map[pp] == 0) {
                    map[pp] = map[pos] + 1;
                    if (pp == x) {
                        return map[pp];
                    }
                    q.push(-pp);
                }
                int np = pos + a;
                if (np < 6000 && map[np] == 0) {
                    map[np] = map[pos] + 1;
                    if (np == x) {
                        return map[np];
                    }
                    q.push(np);
                }
            }
        }
        return -1;
    }
};

오른쪽, 왼쪽으로 가는 경우가 있으므로, bfs 오른쪽, 왼쪽 으로 탐색하면 최단경로(개수) 를 찾을 수 있다.
0개, 1개인 경우는 바로 처리해 주고, a 를 큐에 넣어서 이 위치부터 탐색한다.
탐색할 지도를 6000 만큼 잡아둔다.

• [1998], a = 1999, b = 2000, x = 2000 과 같은 입력이 있는데, 이런 경우, 오른쪽으로 3번 이동해야 한다.
• forbidden max값이랑 x 값을 사용해서 정확한 크기를 구해도 될듯.
• 큐에 카운트와 위치를 같이 저장하면 굳이 지도 변수를 안잡아도 될듯.

오른쪽으로는 항상 탐색, 왼쪽으로는 연속으로 두번 탐색하지 못하게 flag처리(여기서는 음수) 해 주면 된다.
x 에 도착하면 카운트 리턴, 도착 못하면 -1 리턴.

Time: O(x)

• 지도의 크기를 x 에 비례하게 잡아놓았으므로, 모든 구역을 bfs 하는 시간 x

Space: O(x)

• 지도 크기 x, 큐 크기 x