백준 1326 파이썬 코드 답안

문제

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

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

입력

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

출력

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

문제 풀이 

먼저 문제를 확인하면, 개구리는 현재 징검다리 위치에 적혀있는 숫자의 배수만큼 뛴다고 한다. 처음에 문제를 풀 때 틀렸는데, 그 이유는 배수가 양의 배수만큼만 뛴다고 생각해서였다. 개구리는 현재 징검다리 위치에 적혀있는 숫자의 양의 배수, 음의 배수만큼 뛰는 녀석이라고 보면 된다. 

이걸 알게 되면 문제풀이는 아주 쉬워진다. 처음 시작지점에 적혀있는 수의 배수만큼 양의 방향, 음의 방향만큼 뛴다. 뛰는 것은 1과 N 사이의 좌표에서만 뛸 수 있다. 그리고 뛴 좌표를 모드 큐에 넣어준다.

이후에는 Que에 값이 있는 동안만 반복하는 코드를 짯다. Que에서 확인해야 할 좌표를 하나 가지고 온다. 그리고 그 좌표에 적혀있는 숫자를 확인하고, 배수만큼 전 구간을 반복한다. 반복하면 해야하는 활동은 현재 위치에서 1번을 더 뛴 것보다 적은 숫자가 뛸 곳에 적혀져 있으면 아무것도 하지 않고 지나간다.

반면에 현재 위치에서 1번을 더 뛴 값이 뛸 곳에 이미 기록되어있는 점프의 횟수보다 작게 될 경우에는 최소값을 업데이트 해준다. 그리고 이 위치부터 다시 한번 최소값을 업데이트 해야하기 때문에 큐에 해당 좌표를 넣어준다.

이런 식으로 큐가 하나도 없을 때까지 반복해주면 된다. 

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
d = [100000000 for _ in range(n+1)]
v = [0]
temp = list(map(int,sys.stdin.readline().split()))
for i in temp :
    v.append(i)
a,b = map(int,sys.stdin.readline().split())


que = deque()
my_cnt = 1
while a + v[a] * my_cnt <= n : 
    d[a + v[a] * my_cnt] = 1
    que.append(a + v[a] * my_cnt)
    my_cnt += 1

my_cnt = 1
while a - v[a] * my_cnt >= 1 : 
    d[a - v[a] * my_cnt] = 1
    que.append(a - v[a] * my_cnt)
    my_cnt += 1

while que :
    q = que.popleft()
    my_cnt = 1
    while q + v[q] * my_cnt <= n : 
        if d[q + v[q]*my_cnt] > d[q] + 1 :
            d[q + v[q]*my_cnt] = d[q] + 1
            que.append(q + v[q]*my_cnt)
        my_cnt +=1
    my_cnt = 1
    while q - v[q]*my_cnt >= 1 :
        if d[q - v[q]*my_cnt] > d[q] + 1 :
            d[q - v[q]*my_cnt] = d[q] + 1
            que.append(q - v[q]*my_cnt)
        my_cnt += 1


if d[b] == 100000000 :
    print(-1)
else :
    print(d[b])