[Baekjoon] 4연산 / Python, 파이썬 / 14395

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

14395번: 4연산

문제 설명

문제

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

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

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

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 

연산의 아스키 코드 순서는 '*', '+', '-', '/' 이다.

예제 입력 1

7 392

예제 출력 1

+*+

예제 입력 2

7 256

예제 출력 2

/+***

예제 입력 3

4 256

예제 출력 3

**

예제 입력 4

7 7

예제 출력 4

0

예제 입력 5

7 9

예제 출력 5

-1

예제 입력 6

10 1

예제 출력 6

/

문제 풀이

import sys
from collections import deque

input = sys.stdin.readline


A, B = map(int, input().split())


def bfs(x):
    q = deque([(x, '')])
    visited = set([x])
    while q:
        now, opers = q.popleft()
        if now > int(1e9):
            continue
        if now == B:
            return opers
        for oper in ['*', '+', '-', '/']:
            if oper == '*':
                next = now * now
            elif oper == '+':
                next = now + now
            elif oper == '-':
                next = now - now
            elif oper == '/':
                next = 1
            if next not in visited:
                q.append((next, opers + oper))
                visited.add(next)
    
    return -1

if A == B:
    print(0)
    sys.exit(0)
print(bfs(A))