[파이썬] 백준 14395번: 4연산 (BFS)

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 복사

/+***

 

from collections import deque
import sys

s,t=map(int,input().split())
if s==t:
    print(0)
    sys.exit()
visited=set() # 방문 처리 집합 (해당 문제처럼 방문할수있는 수가 무한이면 배열대신 집합으로 처리) 
flag=False # 도달 여부
q=deque()
q.append((s,'')) # 처음 숫자 s, 거쳐간 연산자 string ''
while q:
    x,y=q.popleft()
    if x==t:
        print(y)
        flag=True
        break
    if x>int(1e9): # x가 1e9보다 크면 더이상 진행할 필요없으므로 continue
        continue
    a=x+x # 경우 1
    b=x-x # 경우 2
    c=x*x # 경우 3
    d=x/x # 경우 4
    # 사전순으로 연산 수행
    if c not in visited:
        q.append((c,y+'*'))
        visited.add(c)
    if a not in visited:
        q.append((a,y+'+'))
        visited.add(a)
    if b not in visited and b>0:
        q.append((b,y+'-'))
        visited.add(b)
    if d not in visited and d>0:
        q.append((d,y+'/'))
        visited.add(d)

if flag==False:
    print(-1)