문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s s; (출력: )
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

# 15591
import sys
input = lambda: sys.stdin.readline().strip()

# list 자료구조에서 in 은 시간복잡도 O(N)을 갖지만,
# set  자료구조에서 in 은 시간복잡도 O(1)을 가진다.

from collections import deque

s, t = map(int, input().split())
visited = set()

def bfs(s, t):
    global visited
    queue = deque()
    queue.append((s, t, ""))
    visited.add(s)
    
    while queue:
        s, t, oper = queue.popleft()
        if s == t:
            return oper
        
        if 1 < s*s <= 10**9 and s*s not in visited:
            visited.add(s*s)
            queue.append((s*s, t, oper + "*"))
            
        if 1 < s+s <= 10**9 and s+s not in visited:
            visited.add(s+s)
            queue.append((s+s, t, oper + "+"))
            
        if 0 not in visited:
            visited.add(0)
            queue.append((0, t, oper + "-"))
            
        if 1 not in visited:
            visited.add(1)
            queue.append((1, t, oper + "/"))
            
    return -1

oper = bfs(s, t)
if oper:
    print(oper)
else:
    print("0")

백준 14395 4연산