이번 문제는 BFS와 DP를 함께 사용하여 해결하였다. BFS로 현재 칸에서 점프할 수 있는 칸에 대한 정보를 담는다. 이때 dp리스트에 들어있는 값을 비교하여 현재 카운팅변수+1보다 다음 칸 dp값이 더 클 경우에만 다음칸에 대한 정보를 담게 된다. 이 과정에서 dp리스트를 갱신한다. BFS탐색이 끝난 후 dp[n-1]이 초기값 1e9로 남아있는 경우에는 접근하지 못하는 경우이므로 -1로 갱신해주어야 한다.

Code

import collections
n=int(input())
arr=list(map(int, input().split()))
dp=[1e9 for _ in range(n)]
def bfs():
    q=collections.deque()
    q.append((0, 0))
    dp[0]=0
    while q:
        cur, cnt=q.popleft()
        if arr[cur]==0:
            continue
        for i in range(1, arr[cur]+1):
            nxt=cur+i
            if 0<=nxt<n and dp[nxt]>cnt+1:
                dp[nxt]=cnt+1
                q.append((nxt, cnt+1))
bfs()
if dp[n-1]==1e9:
    dp[n-1]=-1
print(dp[n-1])