개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다.
징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.
이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.
N
bridge
start
destination
dq
check
break_check
now
타입 : int
저장 데이터 : 현재 위치한 징검다리
징검다리 개수 입력받기 (N)
징검다리 마다 갈 수 있는 거리 입력 ( bridge )
출발지, 도착지 입력받기 ( start, destination )
deque를 사용하여 큐 생성 ( dq )
시작점을 큐에 넣기 ( dq.append(start - 1) ) [리스트는 0부터 시작이므로 - 1 ]
한번 방문했던 곳은 check 리스트에 표시하기 (check) [초기 값을 -1 로하고 들렀던 곳은 업데이트, 시작점은 0으로 업데이트 하고 시작]
큐의 가장 앞에 있는 값을 pop lift 를 통해 받아오기 ( now )
조건문을 통해 이동 가능한 거리 일 경우 위치를 dq에 저장한 후 check 리스트 업데이트
조건문을 통해 현재 위치와 도착점을 비교해서 만약 같다면 중단하고 check 리스트를 통해 걸린 횟수를 출력, 이중 for문을 탈출하기 위해 break_check = True 변환
만약 break_check = True 이면 break
위 7번부터 10번까지 while문을 통해 큐가 빌때 까지 반복
만약 반복문을 모두 돌았는데도 불구하고 check 리스트의 도착점 부분이 -1 로 업데이트가 되어있지 않다면 -1 을 출력
import sys
from collections import deque
N = int(sys.stdin.readline()) # 징검다리의 개수를 입력
bridge = list(map(int, sys.stdin.readline().split())) # 징검다리 마다 갈 수 있는 거리 입력
start, destination = map(int, sys.stdin.readline().split()) # 시작점, 도착점 입력
dq = deque()
dq.append(start - 1) # 시작점을 큐에 넣기
check = [-1] * N # check 리스트 생성 [ 한번 갔던 곳을 체크하기 위해! ]
check[start - 1] = 0 # 시작점을 check 리스트에 저장
break_check = False # 이중 for 문을 탈출하기 위한 변수
while dq: # 큐가 빌 때 까지 반복
now = dq.popleft()
for n in range(N): # 징검 다리 수 만큼 반복 [ 배수만큼 이동 가능하므로 ]
if (n - now) % bridge[now] == 0 and check[n] == -1: # 음수로도 이동이 가능하므로 n - now 로 값 지정
dq.append(n) # 위치 저장
check[n] = check[now] + 1 # 체크
if n == destination - 1: # 도착점과 현재 위치가 같다면
print(check[n])
break_check = True
break
if break_check:
break
if check[destination - 1] == -1:
print(-1)