재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 라고 했을 때, 재환이는 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.
재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.
첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 (0 ≤ ≤ 100)가 주어진다.
재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.
점프한 인덱스 idx
와 점프 횟수 cnt
를 큐에 넣어준다.
큐의 초기값 : [0, 0]
큐 안에 값 idx
와 cnt
이 존재하면 꺼낸다.
cnt + 1
과 점프한 위치 idx + i
를 큐에 넣는다.idx
가 jump
리스트의 가장 마지막에 도달했다면, cnt
를 반환하고 멈춘다.import sys
from collections import deque
input = sys.stdin.readline
# 1xN 크기 미로
n = int(input())
jump = list(map(int, input().split()))
visited = [False] * n
# jump[i]이하만큼 점프 가능
# 최소 몇번 점프를 해야하는 가
def minjump(idx, cnt):
queue = deque()
queue.append([idx, cnt])
while queue:
idx, cnt = queue.popleft()
if idx == n - 1:
return cnt
for i in range(1, jump[idx] + 1):
if idx + i < n and not visited[idx + i]:
visited[idx + i] = True
queue.append((idx + i, cnt + 1))
return -1
print(minjump(0, 0))
i
에서 1 ~ jump[i]
범위인 j
만큼 점프한다.i
-> (i + j)
로 점프dp[i+j]
의 기록이 없으면, 점프 이전 위치인 i
의 점프 기록인 dp[i]
에서 1번 점프한 값을 넣는다.dp[i+j] = dp[i] + 1
dp[0] = 0
이다.-1
을 출력한다.import sys
input = sys.stdin.readline()
n = int(input())
jump = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
for j in range(1, jump[i] + 1):
if i + j < n and dp[i+j] == 0:
dp[i+j] = dp[i] + 1
if dp[1:].count(0):
print(-1)
else:
print(dp[n-1])