[백준/Python] 11060 점프점프

 

📌 문제 탐색하기

• 미로의 크기는 1xN (1 ≤ N ≤ 1,000)
• 각 칸에는 정수 A(i) (0 ≤ A(i) ≤ 100)가 쓰여있음
  • 각 칸에 쓰인 수 이하만큼 오른쪽으로 떨어진 칸으로 한번에 점프 가능
• 재환이가 미로의 가장 왼쪽 끝에서 가장 오른쪽 끝으로 가려고 할 때, 최소 몇 번 점프해야 갈 수 있는지 구하기
  • 갈 수 없는 경우 -1 출력

이 문제는 주어진 정보를 그래프로 표현할 수 있고, 최소 횟수로 도달하는 경로를 구하는 것이므로 BFS가 적합하다. 여기서 미로의 각 칸들을 정점으로 볼 수 있고, 각 칸에서 점프 가능한 칸들로 이동하는 것을 간선으로 해석할 수 있다. BFS는 탐색 과정에서 거리가 짧은 노드부터 방문하므로, 처음으로 목표 지점에 도달한 순간이 최단 거리라는 것을 보장한다. 이를 이용해 칸을 하나씩 방문하여 점프를 시도하고, 최소 횟수를 찾으면 된다.

 

시작점에서 점프할 수 있는 모든 칸을 확인하면서 최단 거리로 끝 지점에 도달하는 순간을 찾는 것이므로, BFS 탐색 시 각 칸을 최대 한 번씩 방문한다. 따라서 BFS 탐색은 미로의 길이 N에 비례하는 O(N)의 시간복잡도를 가지게 된다. 그리고 각 탐색 회차마다 현재 칸에서 이동할 수 있는 칸은 최대 칸에 쓰인 수만큼이지만, 제한된 간선을 모두 탐색해도 상수 시간에 해당한다. 따라서 이 문제를 BFS로 풀이 했을 경우의 최종 시간 복잡도는 O(N)이다. 

 

---

📌 코드 설계하기

1. 미로의 크기 N과 미로의 각 칸에 쓰인 숫자 정보 A 리스트로 입력받기
2. 미로의 크기가 1인 경우 탐색 필요없이 최소 횟수 0 출력
3. 큐를 생성하고, 큐에 시작위치의 인덱스와 현재 점프 횟수(0,0) 넣기
4. 방문 체크용 리스트 visited를 False로 초기화
5. 각 칸에서 점프할 수 있는 최대 범위를 순회하며 큐에 다음 칸 추가
   1. 새로운 칸에 도달할 때마다 방문 체크 후 점프 횟수 1 증가하여 큐에 추가
   2. 목표 지점에 도달한 경우 점프 횟수 출력

 

 

---

📌 정답 코드

from collections import deque

def min_jumps(N, A):
    if N == 1:
        return 0

    q = deque([(0, 0)])
    visited = [False] * N
    visited[0] = True

    while q:
        idx, jumps = q.popleft()

        # A[idx]의 범위 내에서 가능한 점프를 확인
        for i in range(1, A[idx] + 1):
            next_idx = idx + i
            if next_idx >= N - 1:
                return jumps + 1
            if not visited[next_idx]:
                visited[next_idx] = True
                q.append((next_idx, jumps + 1))

    return -1

N = int(input())
A = list(map(int, input().split()))
print(min_jumps(N,A))