[탐색/BFS] 백준 11060 점프 점프 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11060번: 점프 점프

 

 

 

2. 문제 풀이

 1칸부터 N칸까지 있으며 각 칸에 쓰인 숫자만큼 최대로 점프할 수 있습니다.

 

2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python

[탐색/BFS] 백준 1697 숨바꼭질 - Python

 숨바꼭질 문제와 비슷하며, BFS를 이용해서 풀 수 있습니다.

 

 

3. 코드

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

# 입력
N = int(input())
graph = list(map(int, input().split()))

if N == 1:
    print(0)
else:
    # bfs
    visited = [0]*(N+1)
    queue = deque([1])
    
    while queue:
        x = queue.popleft()
        if x + graph[x-1] >= N:
            print(visited[x]+1)
            break
        for i in range(1, graph[x-1]+1):
            nx = x+i
            if visited[nx] == 0:
                queue.append(nx)
                visited[nx] = visited[x]+1
    else:
        print(-1)

 N이 1일수도 있습니다. 1칸만 있다면 점프를 하지 않고도 도착할 수 있습니다.