문제
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.
제한사항
입출력 예
1
2
3
4
5
6
7
8
| 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
|
1
2
3
4
5
6
7
| 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
|
1
2
3
4
5
| 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.
|
풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public:
bool canReach(vector<int>& arr, int start) {
stack<int> s;
// checker for avoid visited twice
vector<bool> visited(arr.size(), true);
// DFS
s.push(start);
while(!s.empty()){
auto index = s.top();
s.pop();
// set 'true' on now index;
visited[index] = false;
// found
if(arr[index] == 0)
return true;
// jump left from now index as much as now index's value
int leftIndex = index - arr[index];
if(leftIndex >= 0 && visited[leftIndex])
s.push(leftIndex);
// jump right from now index as much as now index's value
int rightIndex = index + arr[index];
if(rightIndex < arr.size() && visited[rightIndex])
s.push(rightIndex);
}
return false;
}
};
|
