문제

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

import sys

input = lambda: sys.stdin.readline().strip()

from collections import deque

n = int(input())
graph = list(map(int, input().split()))
a, b = map(int, input().split())
a, b = a - 1, b - 1
visited = [10000] * n


def bfs(a, b, count=0):
  queue = deque()
  queue.append((a, b, count))
  while queue:
    a, b, count = queue.popleft()
    if visited[a] > count:
      visited[a] = count
    if visited[b] != 10000:
      break
    for i in range(graph[a], n, +graph[a]):
      if 0 <= a + i < n and visited[a + i] >= count + 1:
        queue.append((a + i, b, count + 1))
    # 개구리가 앞으로 점프하는 경우
    for i in range(graph[a], n, +graph[a]):
      if 0 <= a - i < n and visited[a - i] >= count + 1:
        queue.append((a - i, b, count + 1))
    # 개구리가 뒤로 점프하는 경우


bfs(a, b)
if visited[b] == 10000:
  visited[b] = -1

print(visited[b])

백준 1326 폴짝폴짝