음수가 아닌 정수 배열 arr이 있다고 가정하면 처음에는 배열의 시작 인덱스에 위치합니다. 인덱스 i에 있을 때 i + arr[i] 또는 i - arr[i]로 이동할 수 있습니다. 값이 0인 인덱스에 도달할 수 있는지 확인합니다. 언제든지 어레이. 따라서 입력이 arr =[4,2,3,0,3,1,2]이고 5에서 시작하면 출력은 5 → 4 → 1 → 3 또는 5 → 6 → 이동과 같이 true가 됩니다. 4 → 1 → 3.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=arr의 크기
- 대기열 q를 정의하고, q에 시작을 삽입하고, 방문이라는 집합을 정의하고, 방문 집합에 시작을 삽입
- 대기열이 비어 있지 않은 동안
- curr :=q의 앞 요소, q에서 앞 요소 삭제
- 배열[curr]이 0이면 true를 반환합니다.
- curr + arr[curr]
- q에 curr + arr[curr] 삽입
- 방문한 항목에 curr + arr[curr] 삽입
- curr - arr[curr]>=0이고 curr - arr[curr]이 방문한 집합에 없으면
- curr 삽입 - q에 arr[curr]
- insert curr - 방문에 [curr] 삽입
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
queue <int> q;
q.push(start);
set <int> visited;
visited.insert(start);
while(!q.empty()){
int curr = q.front();
q.pop();
if(arr[curr] == 0)return true;
if(curr + arr[curr] < n && !visited.count(curr + arr[curr])){
q.push(curr + arr[curr]);
visited.insert(curr + arr[curr]);
}
if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])){
q.push(curr - arr[curr]);
visited.insert(curr - arr[curr]);
}
}
return false;
}
};
main(){
vector<int> v = {4,2,3,0,3,1,2};
Solution ob;
cout << (ob.canReach(v, 5));
} 입력
[4,2,3,0,3,1,2] 5
출력
1