[백준 11060번] 점프 점프 (Python)

> 파이썬, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

📖 문제 : 점프 점프 (Python)

 

 

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

 

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

 

예제 입력 1 

10
1 2 0 1 3 2 1 5 4 2

 

예제 출력 1 

5

 

 

내 코드

from collections import deque

N = int(input())
board = list(map(int, input().split()))
visited = [0] * N
queue = deque([])

if N == 1:
    print(0)
else:
    for i in range(1, board[0] + 1):
        queue.append((0, i, 0))  # 출발점, 움직일 칸 수, 점프 수
    visited[0] = 1

    while queue:
        # print(queue)
        # print(visited)
        start_point, move, jump_cnt = queue.popleft()

        if start_point == N - 1:
            print(jump_cnt)
            break

        end = (start_point + move if start_point + move < N else N - 1)

        for i in range(end, start_point - 1, -1):

            if visited[i] == 0:
                visited[i] = 1
                queue.append((i, board[i], jump_cnt + 1))  # 출발점, 움직일 칸 수, 점프 수

    else:
        print(-1)

 

 

 

Point ! ⭐️ 

• 저는 BFS 방법을 사용했습니다.
  
  예를 들어, N = 5인 미로가 (5, 4, 3, 2, 1) 로 되어있다면,
  1, 2, 3, 4 번 자리 모두 5번 자리로 갈 수 있습니다. 하지만, 가장 최소로 갈 수 있는 방법은 5을 가진 1번자리 이기 때문에, 이 걸 이용해서 visited 리스트를 만들어 반복 횟수를 줄였습니다. 
  
  결국, 앞(1)에서 가고자 하는 자리에 이미 갈 수 있다면, 그 앞(1)보다 더 뒤(2,3,4,..)에 자리에서 굳이 갈 필요가 없기 때문에, 
  이미 갈 수 있는 길이라면 갈 수 있는 자리의 visited 값을 1로 바꿔주며 탐색했습니다.
  
  
  

 

 

 

 

백준

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

11060번: 점프 점프