[LeetCode] 1306. Jump Game III

https://leetcode.com/problems/jump-game-iii/

Jump Game III - LeetCode

Jump Game III - Medium

 

수로 이루어진 vector arr가 주어지고, start index가 주어진다.

start 에서 시작하여 다음과 같이 이동한다.

start + arr[start] 로 이동하거나 start - arr[start]로 이동한다.

이 때, 이동한 index에서 arr[index] = 0 이 된다면 true를, 어떻게 해서든 0이 되는곳에 도달할 수 없다면 false를 return 한다.

 

BFS를 사용하면 해결된다.

queue를 만들어 start를 넣고,

queue가 비어있지 않을때,

일단 arr[idx] == 0 이면 바로 true를 return한다.

아니라면,

start+arr[idx] 가 arr.size() 보다 작다면 start+arr[idx]를 추가

start-arr[idx] 가 0 이상이면 start-arr[idx]를 추가해주고 반복해준다.

 

이 때, 주의할 점은 chk 배열을 0으로 초기화해 만들어 index를 거칠때마다 chk[idx] 를 1로 바꿔준다.

queue에 추가하는 작업을 할 때, 이 chk[idx] 가 0인 경우에만 추가해주도록 하자.

이래야 중복상황을 피할 수 있다.

 

전체 풀이 코드

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