돌다리[백준 12761]

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

 

방문의 이동 횟수를 잘 기록 해주면 된다. 

from collections import deque 

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

visited =[-1]*(100000+1 )

def bfs(start): 
    q = deque() 
    q.append((start,0)) 
    visited[start]=0 
    while q :
        x ,dist= q.popleft() 
        if x == m :
            return dist 
        if x+1 < 100000+1 and visited[x+1] == -1 :
            visited[x+1] =dist + 1  
            q.append((x+1 , dist+1 ))
        if 0<=x-1 and visited[x-1] == -1 :
            visited[x-1] =dist + 1  
            q.append((x-1 , dist+1 ))
        if x+a < 100000+1 and visited[x+a] == -1 :
            visited[x+a] =dist + 1  
            q.append((x+a , dist+1 ))
        if x+b < 100000+1 and visited[x+b] == -1 :
            visited[x+b] =dist + 1  
            q.append((x+b , dist+1 ))
        if 0<=x-a  and visited[x-a] == -1 :
            visited[x-a] =dist + 1  
            q.append((x-a , dist+1 ))
        if 0<=x-b  and visited[x-b] == -1 :
            visited[x-b] =dist + 1  
            q.append((x-b , dist+1 ))
        if x*a  < 100000+1 and visited[x*a] == -1: 
            visited[x*a] =dist + 1  
            q.append((x*a , dist+1 ))
        if x*b< 100000+1 and visited[x*b] == -1 :
            visited[x*b] =dist + 1  
            q.append((x*b , dist+1 ))

ans =bfs(n) 
print(ans)