꽤 재밌고 쉽고 BFS를 쉽게 배울 수 있는 문제를 가지고 왔다.

BOJ 1326 - 폴짝폴짝 링크
(2022.11.16 기준 S2)

문제

각 징검다리에는 숫자가 쓰여 있고, 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.
a에서 b 징검다리로 가려고 한다면, 최소 점프 횟수 출력

알고리즘

모든 간선에는 가중치가 없으므로 (일정하므로), BFS나 DFS. 그리고 최단 거리를 구해야 하므로, BFS를 사용해야 한다.

풀이

아래와 같은 징검다리와 queue 상태를 살펴보자.
시작한 곳은 굵게. 만약, 방문체크한 곳에 간다면 그 곳은 기울임꼴로 나타내겠다.

queue = [[0, 0]]
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, -, -, -, -, -, -, -]

queue = [[4, 1]]
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, -, -, -, 1, -, -, -]

queue = [[1, 2], [7, 2]]
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, 2, -, -, 1, -, -, 2]

queue = [[7, 2]]
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, 2, -, -, 1, -, -, 2]

queue = [[3, 3], [5, 3]]
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, 2, -, 3, 1, 3, -, 2]

queue = [[5, 3], [6, 4]]
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, 2, -, 3, 1, 3, 4, 2]

queue = [[6, 4]]
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, 2, -, 3, 1, 3, 4, 2]

queue = []
징검 [4, 3, 2, 3, 3, 2, 3, 2]
점프 [0, 2, -, 3, 1, 3, 4, 2]

방문체크한 곳에 간다면 스킵할 수 있는 이유가 보인다.
이미 더 적은 횟수로 그 곳에서 출발했었기 때문.

먼저 넣었던 원소를 우선으로 빼내야 하기 때문에 queue를 사용해야 하고, 징검다리에 적혀져 있는 수의 배수로 갈 수 있으니깐 range()로 구현하면 된다.

코드

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

N = int(input()) # 징검다리의 개수
step = list(map(int, input().split())) # 각 징검다리
a, b = map(int, input().split()) # 출발, 도착
a -= 1; b -= 1 # 0-based index

queue = deque([[a, 0]]) # a부터 시작
visited = [False] * N # 방문체크
visited[a] = True # a 체크

while queue:
    here, stepped = queue.popleft() # 현재 위치, 점프 횟수
    if here == b: # 현재 위치가 도착해야 하는 b 이라면
        print(stepped) # 점프 횟수 출력 후 중단
        break

    # here, here + step[here], here + step[here] * 2, ...
    for there in range(here, N, step[here]):
        if not visited[there]: # 방문하지 않은 곳이어야 한다.
            queue.append([there, stepped + 1])

    # here - step[here], here - step[here] * 2, ...
    for there in range(here - step[here], -1, -step[here]):
        if not visited[there]:# 방문하지 않은 곳이어야 한다.
            queue.append([there, stepped + 1])

# 방문 가능한 모든 곳을 방문했지만 b에 도착하지 않았다면 -1 출력
# 즉, bfs가 중단되지 않았다면. queue가 모두 비어졌다면.
else:
    print(-1)