[백준/Python] 11060번: 점프 점프

문제

https://www.acmicpc.net/problem/11060

11060번: 점프 점프

---

문제 요약

재환이는 n개의 칸으로 이루어진 미로의 가장 왼쪽 끝 칸에 존재한다.

 

칸에 쓰여져 있는 수만큼 오른쪽으로 떨어진 칸으로 이동할 수 있을 때, 가장 오른쪽 끝 칸으로 이동할 수 있는 최소 점프 횟수를 출력한다.

 

가장 오른쪽 끝 칸으로 이동할 수 없는 경우 -1을 출력한다.

---

코드

from collections import deque

def min_jump(arr):
    n = len(arr)
    if n <= 1:
        return 0

    dp = [-1] * n
    dp[0] = 0
    # dp[i]는 i번째 칸까지 이동하는데 사용되는 점프 개수
    
    queue = deque()
    queue.append(0)
    
    # deque를 이용한 BFS
    while queue:
        cur = queue.popleft()
        for jump_size in range(1, arr[cur] + 1):
            next_index = cur + jump_size
            if next_index >= n: # 입력받은 배열의 인덱스를 초과하면
                break 
            if dp[next_index] == -1: # 한 번 갱신된 dp는 다시 갱신 X
            # i 칸까지 이동 방법이 많아도 최소 점프로 가는 방법이 먼저 dp[i]에 저장되기 때문
                dp[next_index] = dp[cur] + 1 # dp 갱신
                queue.append(next_index) # 큐에 다음 인덱스 추가

    return dp[n - 1]

n = int(input())

arr = list(map(int, input().split()))

result = min_jump(arr)

print(result)

---

코드 설명

1. 0번째 칸부터 큐에 넣고 BFS 탐색을 진행한다.

+ (1 ~ 현재 칸에 적혀진 수 + 1) + 현재 인덱스 = 다음 인덱스

+ 입력 받은 배열의 인덱스를 초과하지 않도록 한다.

 

2 - 1. i 칸까지 이동하는데 사용되는 최소 점프 횟수를 저장하는 메모이제이션 테이블 dp를 이용한다.

 

2 - 2. 이미 갱신된 dp는 다시 갱신하지 않는다.

+ 넓이 우선 탐색 (BFS)를 이용하면 i 칸까지 이동 방법이 많아도 최소 점프로 가는 방법이 먼저 dp[i]에 저장된다.