문제 설명
음이 아닌 정수로 구성된 배열 arr가 주어지고, 우리는 배열의 특정 시작 인덱스(start)에 위치해 있습니다. 현재 인덱스 i에 있을 때, i + arr[i] 또는 i − arr[i]로 점프할 수 있습니다. 이때 목표는 값이 0인 인덱스에 도달할 수 있는지 판별하는 것입니다. 단, 어떤 경우에도 배열의 범위를 벗어나서는 안 된다는 점에 유의해야 합니다.
예를 들어, 입력이 arr = [4,2,3,0,3,1,2]이고 시작 인덱스가 5라면 결과는 true입니다. 왜냐하면 5 → 4 → 1 → 3 또는 5 → 6 → 4 → 1 → 3 경로를 통해 값이 0인 인덱스(3번)에 도달할 수 있기 때문입니다.
해결 접근 방식
이 문제는 그래프 탐색 관점에서 바라볼 수 있습니다. 각 인덱스를 노드로 생각하고, 점프 가능한 위치를 간선으로 연결하면 됩니다. 따라서 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 이미 방문한 인덱스를 기록하여 무한 루프를 방지하는 것이 핵심입니다.
알고리즘의 진행 순서는 다음과 같습니다.
- n := 배열 arr의 크기로 설정합니다.
- 큐 q를 생성하고 start를 삽입합니다. 방문 여부를 추적하기 위한 집합(visited)을 만들고 start를 추가합니다.
- 큐가 빌 때까지 다음 과정을 반복합니다.
- curr := q의 맨 앞 요소를 꺼내고, 해당 요소를 큐에서 제거합니다.
- arr[curr]이 0이라면 true를 반환합니다.
- curr + arr[curr] < n이면서 아직 방문하지 않았다면, 해당 인덱스를 큐와 visited에 추가합니다.
- curr − arr[curr] ≥ 0이면서 아직 방문하지 않았다면, 해당 인덱스를 큐와 visited에 추가합니다.
- 반복이 끝날 때까지 0에 도달하지 못했다면 false를 반환합니다.
구현 예제
아래 C++ 코드를 통해 더 자세히 이해해 보겠습니다.
#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
출력값 1(true)은 시작 인덱스 5에서 출발하여 값이 0인 인덱스에 성공적으로 도달할 수 있음을 의미합니다.