14395: 4연산

• 최소 연산 횟수 + 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력 -> bfs로 풀이
• 연산의 순서를 '*' -> '+' -> '-' -> '/'로 진행함
• 한 가지 막혔던 부분이 s를 t로 바꿀 수 없는 경우였는데, 이 경우는 t가 "1 <= t <= 10**9"까지의 범위이기 때문에, nexts가 해당 조건을 만족할 경우에만 queue에 집어넣는 방식으로 해결함
• 시간 복잡도를 고려하여 중복 제거를 위한 visit 변수를 set으로 처리함

import sys
from collections import deque

def bfs():
    queue = deque([])
    queue.append([s, ''])
    visit.add(s)

    while queue:
        currs, op = queue.popleft()

        if currs == t:
            print(op)
            return

        nexts = currs * currs
        if 1 <= nexts <= 10**9 and nexts not in visit:
            queue.append([nexts, op + '*'])
            visit.add(nexts)
        
        nexts = currs + currs
        if 1 <= nexts <= 10**9 and nexts not in visit:
            queue.append([nexts, op + '+'])
            visit.add(nexts)

        nexts = currs - currs
        if 1 <= nexts <= 10**9 and nexts not in visit:
            queue.append([nexts, op + '-'])
            visit.add(nexts)

        if currs != 0:
            nexts = currs // currs
            if 1 <= nexts <= 10**9 and nexts not in visit:
                queue.append([nexts, op + '/'])
                visit.add(nexts)
    print(-1)

s, t = map(int, sys.stdin.readline()[:-1].split())
if s == t:
    print(0)
else:
    visit = set()
    bfs()