[백준] 14395번 - 4연산

📩 출처

문제

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

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

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

입력

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

출력

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

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

👉 생각

• 대놓고 BFS 문제였다.
• 4가지 연산을 하면서 나오는 값들을 너비우선 탐색을 하면서 목적 값이 나오면 연산 과정을 반환한다.
• 찾지 못하면 -1을 반환한다.

from collections import deque

def bfs():
    q = deque([(s, '')])
    check = set()
    check.add(s)
    while q:
        num, res = q.popleft()

        if num == t:
            return res

        for code in ['*', '+', '-', '/']:
            if code == '*':
                next = num * num
            elif code == '+':
                next = num + num
            elif code == '-':
                next = num - num
            else:
                if num:next = num // num
            if next not in check and next <= max(s, t):
                q.append((next, res + code))
                check.add(next)

    return -1

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

answer = bfs()
if answer == '':
    print(0)
else:
    print(answer)