BOJ - 12761

백준 문제 링크
돌다리

❓접근법

1. BFS를 사용했다.
2. 방문 처리할 visited 변수와 이동 횟수를 저장할 answer 변수를 만들었다.
3. 문제에서 나온 조건은 현 위치에서

• +1, -1, +A, -A, +B, -B, 곱하기 A, 곱하기 B 총 8개의 경우이다.

4. 아직 방문하지 않았다면 방문 처리를 하고, queue에 i를,
   자식 노드의 값 (answer[i]) = 부모 노드의 값 (answer[v]) + 1을 넣었다.
5. bfs(N)을 실행하고 answer[M]을 출력하면 끝!

👌🏻코드

from collections import deque

A,B,N,M = map(int, input().split())

visited = [False] * 100001
answer = [0] * 100001

def bfs(x):
    queue = deque()
    queue.append(x)
    
    visited[x] = True
    
    while queue:
        v  = queue.popleft()
        
        for i in [v-1, v+1, v-A, v-B, v+A, v+B, v*A, v*B]:
            if (0 <= i <= 100000) and not visited[i]:
                visited[i] = True
                queue.append(i)
                answer[i] = answer[v] + 1
                
bfs(N)
print(answer[M])