[백준] 11060번 점프점프(파이썬)

문제

 

11060번: 점프 점프

코드

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit = 10**6

def dist(A, visited):
    q = deque([(0, A[0])])
    while q:
        i, jump = q.popleft()
        for j in range(1, jump + 1):
            if i + j >= N or visited[i + j] != 0:
                continue 
            else:
                visited[i + j] = visited[i] + 1
                q.append(((i + j), A[i + j]))                

N = int(input())
A = list(map(int, input().split()))
visited = [0] * N
          
dist(A, visited)

if N == 1:
    print(0)
else:
    if visited[-1] == 0:
        print(-1)
    else:
        print(visited[-1])

해설

BFS 방법으로 풀어보았다.

맨 처음은 무조건 0, 0이니까 q에 0씩을 넣어주고 for로 점프하는 칸수만큼 뛴다. visited에 점프에 수를 표시했다.

max로 찾으려다가 더 큰수가 있으면 어쩌지 하는 생각에 visited[-1]로 찾았다.

혹시 99%에서 틀렸다면 1칸일 경우 뛰지 않는것을 설정을 안해줘서 틀린 것임으로 꼭 설정해주자!