[BOJ / Python] 11060번 점프 점프

🧩 문제 설명 

input : 배열의 크기, 배열의 값 (점프 가능한 수)

output : 몇번 점프해야 맨 오른쪽 칸에 도착할 수 있는지, 도착할 수 없다면 -1

 

 

🔐 문제 풀이 

❌ 첫번째 시도 - 틀렸습니다

# https://www.acmicpc.net/problem/11060
# 점프 점프

import sys
input = sys.stdin.readline

# 입력
N = int(input().strip())  # 배열의 크기
data = list(map(int, input().split()))


def jump_jump():
    answer = 0  # 점프 횟수
    current = 0  # 현재 위치 (인덱스)
    for _ in range(N):
        if current >= N - 1:
            return answer

        jump = data[current]  # 점프할 수 있는 칸

        current = current + jump  # 현재 위치 업데이트
        answer += 1  # 이동 횟수 +1

    return -1


print(jump_jump())

게시판에 있는 반례들도 모두 제대로 출력되는데,, 왜 ,, 틀렸다는건지 모르겠다😵

아시는 분은 답변 부탁드립니다 > https://www.acmicpc.net/board/view/116963

 

✅ 정답코드 

결국 다른 분의 코드를 참고해 해결했다 💤

# https://www.acmicpc.net/problem/11060
# 점프 점프

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

# 입력
N = int(input().strip())  # 배열의 크기
data = list(map(int, input().split()))
inf = 10_0000_0000


def jump_jump():
    q = deque([0])
    visited = [inf] * N  # 최소 점프 횟수를 구하기 위해 max 값을 저장해둔다. [1000000000, 1000000000, ... ]
    visited[0] = 0
    while q:
        current = q.popleft() # 현재 위치

        if current == N - 1:  # 현재 위치가 마지막 위치인 경우
            return visited[current]

        for jump in range(1, data[current] + 1): # 점프할 수 있는 칸의 크기
            move = current + jump  # 이동 후 위치

            if move > N - 1: # 범위 밖이라면 out
                continue

            if visited[move] > visited[current] + 1:
                visited[move] = visited[current] + 1  # 점프 횟수 +1
                q.append(move)  # 이동한 위치 업데이트

    return -1


print(jump_jump())