백준: 11060 점프 점프

문제

11060번: 점프 점프

 

문제 풀이

 1xN의 미로에는 각 칸에 정수가 적혀있다. 예를 들어 칸에 3이 적혀있다면 현재 위치에서 +1, +2, +3으로 점프할 수 있다. 이때, 최소한으로 점프하여 가장 오른쪽 끝으로 갈 수 있을 경우 점프 횟수를 반환하고 그렇지 않을 경우 -1을 반환하여야 한다.

 

 문제를 풀기 위해서는 BFS를 통해, 현재 위치에서 탐색 가능한 경로를 추가하는 방식을 사용하여 탐색을 진행하면 된다. 만약 BFS로 모든 경우의 수를 탐색하여도 답을 찾지 못하는 경우는 -1을 반환하면 된다.

 

• BFS를 탐색하는데 있어 아래와 같은 조건을 확인하여야 한다.
  • 탐색하고자 하는 인덱스가 N보다 작은가?
    • N보다 커진다면 탐색할 필요가 없다.
    • 인덱스 오류도 발생시킨다.
  • 탐색하고자 하는 칸의 점프 가능한 수가 0보다 큰가?
    • 0이라면 해당 칸에서 점프할 수 없으므로 탐색에서 제외한다.
  • 한 번이라도 방문하지 않았는가?
    • 이미 방문한 경우라면 3칸을 뛰는 경우 현재 칸에서 1, 2, 3 앞의 칸을 방문하게 된다.
    • 따라서 재방문 여부를 확인하여야 한다.

 

코드

from sys import stdin
from collections import deque


def visitable(idx):
    return idx < n and a[idx] > 0 and not visited[idx]


def bfs(start):
    q = deque([start])

    while q:
        idx, cnt = q.popleft()
        if idx + 1 == n:
            return cnt

        for i in range(a[idx] + 1):
            next_idx = idx + i

            if visitable(next_idx):
                visited[next_idx] = True
                q.append((next_idx, cnt + 1))
    return -1


if __name__ == '__main__':
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    visited = [True] + [False] * (n - 1)
    print(bfs([0, 0]))