[Leetcode] 1306. Jump Game III

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

---

음이 아닌 정수 arr 배열과 시작 인덱스 start가 주어진다.

인덱스 i에 있을 때 i+arr[i], i-arr[i] 인덱스로 점프할 수 있다고 할 때 값이 0인 인덱스에 도달할 수 있는지를 구하라.

---

i번째 인덱스를 방문한 적이 있는지를 저장하는 배열을 하나 만들고 시작 인덱스 start부터 i+arr[i], i-arr[i] 인덱스 위치로 탐색하며 이미 방문한 적이 있다면 더 이상 탐색하지 않고 탐색한적이 없으면 방문여부를 true로 갱신한 다음 해당 값이 0이면 true를 반환한다. 해당 값이 0이 아닌 경우 i+arr[i], i-arr[i]가 배열 arr 범위 내부이며 방문한 적 없는 인덱스인 경우 탐색을 이어나간다.

 

시간/공간 복잡도는 O(N). N = |arr|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1306.%20Jump%20Game%20III.cpp