[백준/파이썬/그래프/BFS] 1326번 폴짝폴짝 코딩테스트 연습풀이

문제 출처: https://www.acmicpc.net/problem/1326

1326번: 폴짝폴짝

 

문제

개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.

이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오.

 

입력

첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 징검다리에서 시작하여 b번 징검다리에 가고 싶다는 뜻이다. 징검다리에 쓰여있는 정수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 개구리가 a번 징검다리에서 b번 징검다리로 최소 몇 번 점프하여 갈 수 있는 지를 출력하시오. a에서 b로 갈 수 없는 경우에는 -1을 출력한다.

 

정답

import sys
from collections import deque

def bfs():
    queue = deque([a - 1])
    visited = [-1] * 100000
    visited[a - 1] = 0

    while queue:
        target = queue.popleft()
        for i in range(target, n, arr[target]):
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[target] + 1
                if i == b - 1:
                    return visited[i]
        for i in range(target, -1, -arr[target]):
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[target] + 1
                if i == b - 1:
                    return visited[i]
    return -1

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
a, b = map(int, sys.stdin.readline().split())
print(bfs())

bfs를 이용해서 풀면 되는 문제였습니다.