백준 12761 돌다리 (파이썬)

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

12761번: 돌다리

주어진 조건대로 구현하여 bfs를 진행하면 된다

단, 시작을 0부터하면 예제입력2 같은 경우에 오답이 나오기 때문에 1부터 시작해야한다

from collections import deque
import sys

input = sys.stdin.readline

def bfs():
    q.append(n)
    c[n] = 1
    while q:
        x = q.popleft()
        if x == m:
            print(c[x]-1)
        for i in range(3):
            nx = x + jump[i]
            if nx < limit and not c[nx]:
                c[nx] = c[x] + 1
                q.append(nx)
            nx = x - jump[i]
            if nx > 0 and not c[nx]:
                c[nx] = c[x] + 1
                q.append(nx)
            nx = x * jump[i]
            if nx < limit and not c[nx]:
                c[nx] = c[x] + 1
                q.append(nx)

a, b, n, m = map(int, input().split())
jump = [1, a, b]
limit = 100001
c = [0 for _ in range(limit)]
q = deque()
bfs()