Jump Game III

1306. Jump Game III

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        if (arr[start] == 0) {
            return true;
        }
        int len = arr.size();
        vector<bool> visit(len, false);
        queue<int> q;
        q.push(start);
        visit[start] = true;
        while (!q.empty()) {
            int c = q.front();
            q.pop();
            int f = c + arr[c], b = c - arr[c];
            if (f < len && !visit[f]) {
                if (arr[f] == 0) {
                    return true;
                }
                visit[f] = true;
                q.push(f);
            }
            if (0 <= b && !visit[b]) {
                if (arr[b] == 0) {
                    return true;
                }
                visit[b] = true;
                q.push(b);
            }
        }
        return false;
    }
};

현재 위치에서 갈수 있는 위치가 최대 2가지 이므로 bfs 로 0 을 찾아 간다. 탐색결과 0 찾으면 true 못찾으면 false

n == arr.size()

Time: O(n)
주어진 arr bfs 탐색으로 모든 index 탐색할수 있으므로 루프를 n 회 돌 수 있다.

Space: O(n)
중복 index 방문 방지용 visit array size n, bfs queue 최대로 차게 되는 경우 n/2