[🥈2 / 백준 11060 / 파이썬] 점프 점프

 

11060번: 점프 점프

 

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 A_i라고 했을 때, 재환이는 A_i이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 A_i (0 ≤ A_i ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

 

예제 입력 10 1 2 0 1 3 2 1 5 4 2

예제 출력 5

 

풀이

 

동적 계획법으로도 풀 수 있는 문제이다.

필자는 BFS로 해결하였으므로, BFS 풀이를 포스팅하겠다.

 

각 지점을 방문했는지 확인하는 visited 배열을 만들고 여기에 해당 지점까지 몇 번의 점프로 갈 수 있는지 기록할 것이다.

첫 번째 지점부터 시작하여 여기에 적혀 있는 숫자만큼 오른쪽으로 차근차근 넘어가며 방문한다.

방문하지 않은 곳이었다면, visited 배열을 갱신하고 큐에 넣는다.

 

큐가 비었다면 마지막 지점을 확인하여 0이라면 -1을, 아니라면 그대로 출력한다.

 

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
# 1이라면 시작과 동시에 종료
if n == 1:
    print(0)
    sys.exit()
    
arr = list(map(int,input().split()))
visited = [0]*n
q = deque([(0,arr[0])]) # 현재 위치, 점프 가능 거리

while q:
    pos,jump = q.popleft()
    for i in range(1,jump+1):
        if pos+i >= n or visited[pos+i]:
            continue
        visited[pos+i] = visited[pos]+1
        q.append((pos+i,arr[pos+i]))
print(visited[-1] if visited[-1] else -1)