[파이썬, Python] 백준 12761번 : 돌다리

백준 12761번 : 돌다리

(문제 바로가기)

 

 

내 코드

from collections import deque

# a, b : 스카이 콩콩의 힘
# n : 동규의 현재 위치
# m : 주미의 현재 위치
a, b, n, m = map(int, input().split())
dp = dict()  # 각 돌의 최소 이동 횟수
dp[n] = 0
queue = deque([n])  # n에서 시작

while queue:  # bfs 수행
    curr = queue.popleft()

    for i in {1, -1, a, -a, b, -b}:  # +1칸, -1칸, +A칸, -A칸, +B칸, -B칸 이동
        val = curr + i
        if 0 <= val <= 100000 and val not in dp:
            dp[val] = dp[curr] + 1
            queue.append(val)

    for i in {a, b}:  # A배나 B배의 위치로 이동
        val = curr * i
        if 0 <= val <= 100000 and val not in dp:
            dp[val] = dp[curr] + 1
            queue.append(val)

    if m in dp:  # m에 도달할 수 있는 경우
        break  # 종료

print(dp[m])