[Python3] SWEA 연산 5247

문제 :

자연수 N에 몇 번의 연산을 통해 다른 자연수 M을 만들려고 한다.
사용할 수 있는 연산이 +1, -1, *2, -10 네 가지라고 할 때 최소 몇 번의 연산을 거쳐야 하는지 알아내는 프로그램을 만드시오.
단, 연산의 중간 결과도 항상 백만 이하의 자연수여야 한다.
예를 들어 N=2, M=7인 경우, (2+1) *2 +1 = 7이므로 최소 3번의 연산이 필요한다.

 

접근 :

bfs를 활용해 방문 체크 후 연산을 진행한다.

 

풀이 :

from collections import deque
 
def bfs(N, M):
    queue = deque()
    queue.append((N, 0))
    check = {}
    while queue:
        item, count = queue.popleft()
        if check.get(item, 0): continue
        check[item] = 1
        if item == M: return count
        count += 1
        if 0 < item+1 <= 1000000:
            queue.append((item+1, count))
        if 0 < item-1 <= 1000000:
            queue.append((item-1, count))
        if 0 < item*2 <= 1000000:
            queue.append((item*2, count))
        if 0 < item-10 <= 1000000:
            queue.append((item-10, count))
 
for t in range(int(input())):
    N,M = map(int, input().split())
    print('#{} {}'.format(t+1, bfs(N,M)))