BOJ - 11060

백준 문제 링크
점프 점프

❓접근법

1. BFS를 사용했다.
2. 미로를 리스트 data로 받고,
   방문 처리할 리스트 visited = [False] x (n + 1),
   점프 횟수를 저장할 리스트 answer = [0] x (n + 1) 를 만들어준다.
3. bfs 함수를 만들어보자.
   오른쪽 끝으로 갈 수 있는지 확인할 변수 isFalse = False를 만든다.
   큐가 비어있을 때까지,
   큐에서 원소를 뽑아서 n과 같다면 isFalse = True, break 한다.
4. temp = data[x - 1] 로 지정해 몇 칸을 갈 수 있는지 확인한다.
   적용해야할 조건은 다음과 같다.

for i in range(1, temp + 1):
	if 0 <= x + i <= n:
    	if not visited[x + i]:
        	queue.append(x+i)
            answer[x+i] = answer[x] + 1
            visited[x+i] = True

조건을 적용하고 난 뒤에는 isFalse를 return 하면 된다.
5. 만약 bfs(1)이 False이면 -1을, True이면 answer[n]을 출력 !
bfs(1)로 하는 이유는, 각 리스트를 n + 1의 길이로 만들었기 때문.
그래서 temp도 data[x - 1]로 지정했음.

👌🏻코드

from collections import deque

n = int(input())

data = list(map(int, input().split()))

visited = [False] * (n + 1)
answer = [0] * (n + 1)

def bfs(x):
    queue = deque()
    queue.append(x)
    
    visited[x] = True
    
    isFalse = False
    
    while queue:
        x = queue.popleft()
        
        if x == n:
            isFalse = True
            break
        
        temp = data[x - 1]
        
        for i in range(1, temp + 1):
            if 0 <= x + i <= n:
                if not visited[x + i]:
                    queue.append(x+i)
                    answer[x+i] = answer[x] + 1
                    visited[x+i] = True
                    
    return isFalse

if bfs(1) == True:
    print(answer[n])
else:
    print(-1)