[백준] 11060번 점프 점프 ★★

💡문제접근

• DP로 푸는 것보다는 BFS가 낫겠다고 생각해서 계속 도전했는데 WA를 받았다. 확인해보니 어이없게도 방문한 적이 있거나 만약 인덱싱이 N값 이상이 나오면 continue를 실행시켰어야했는데break를 걸어버려 계속 틀렸던 것이다.

💡코드(메모리 : 34140KB, 시간 : 72ms)

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

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

if N == 1:
    print(0)
    sys.exit()

def BFS():
    queue = deque()
    queue.append((0, li[0]))
    while queue:
        start, jump_cnt = queue.popleft()
        for i in range(1, jump_cnt + 1):
            if start + i >= N or visited[start + i]:
                continue
            visited[start + i] = visited[start] + 1
            queue.append((start + i, li[start + i]))

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

💡소요시간 : 2h