12761번 돌다리

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

---

아이디어

동규가 갈 수 있는 모든 경우를 가면서 현재 위치에서 +1씩 증가시키면 된다.

BFS를 1차원 리스트로 할 수 있는 좋은 문제인 것 같다.

코드

from collections import deque

def bfs(cur):
    queue = deque([])
    queue.append(cur)
    graph[cur] = 0

    while queue:
        cur = queue.popleft()
        for i in [cur + 1, cur - 1, cur + A, cur + B, cur - A, cur - B, cur * A, cur * B]:
            if 0 <= i <= 100000 and graph[i] == -1:
                graph[i] = graph[cur] + 1
                queue.append(i)
                if i == M: return


A, B, N, M = map(int, input().split())
graph = [-1] * 100001
bfs(N)
print(graph[M])