[Leetcode] 1306. Jump Game III

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation: 
All possible ways to reach at index 3 with value 0 are: 
index 5 -> index 4 -> index 1 -> index 3 
index 5 -> index 6 -> index 4 -> index 1 -> index 3 

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true 
Explanation: 
One possible way to reach at index 3 with value 0 is: 
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

난이도: medium

자연수로 이루어진 Array에서 첫 시작점을 주고 점프를 하며 이동하는데, 0에 도달 가능한지 구해라

문제를 보고 DFS로 풀어야겠다 생각했는데

이런식으로 인덱스에서 이동가능한 경우의 수를 확인해보면 연결되는 모습이 보이는데

결과적으로는 그래프의 형태가 나오고 DFS겠구나 생각이 들었다

var canReach = function(arr, start) {
  const visited = new Set(); // visited = { index: arr[index] } index에 도달한적이 있는가?

  const dfs = (index) => {
    if (index < 0 || index > arr.length || visited.has(index)) {
      return false 
    }

    visited.add(index);
    const value = arr[index];
    if (value === 0) {
      return true
    }

    return dfs(index - value) || dfs(index + value)
  }

  return dfs(start);
};

메모리 효율이 좋지 못해서 풀이를 봤는데 대부분 Queue를 이용한 BFS로 풀이한 것으로 보인다