백준 1326 폴짝폴짝(BFS)

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

1326번: 폴짝폴짝

DP문제라고 생각했지만 bfs적으로 바로 생각이 나서 그래프로 풀었다.

 

● 지금 서있는 발판 숫자의 배수만큼 뛰어야하니까 for에서 간격을 data값으로 해준 것

● a to b로 이동해야하는데 a와 b의 크기비교가 문제에 제시하지 않았기 때문에 반대 상황도 고려해야함

 

방문하지 않았던 곳은 큐에 넣어주고 그 곳으로 가기위한 점프수는 popleft한 값에 1번 점프된 곳이니까 +1을 해줘서 저장

 

n = int(input())
data = list(map(int,input().split()))
a,b = list(map(int,input().split()))

from collections import deque

def bfs():
    queue = deque()
    queue.append(a-1)
    dp = [-1] * n
    dp[a-1] = 0

    while queue:
        temp = queue.popleft()
        for k in range(temp,n,data[temp]):
            if dp[k] == -1:
                queue.append(k)
                dp[k] = dp[temp] + 1
                #print(dp)
                if k == b-1:
                    return dp[k]
        for k in range(temp,-1,-data[temp]):
            if dp[k] == -1:
                queue.append(k)
                dp[k] = dp[temp] + 1
                if k == b-1:
                    return dp[k]
    return -1
print(bfs())