백준 14395번 4연산 (Python 3)

Baekjoon online judge 14395번 파이썬

 

링크

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

14395번: 4연산

'-' 연산은 항상 0이고 이는 문제에서 주어진 범위에서 벗어나기 때문에 사용하지 않는다.

'/' 연산은 항상 결과로 1을 낸다.

+,* 연산의 경우일떄 범위에 주의해서 bfs를 하면된다.

 

소스코드

import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline

def bfs(start):
  queue=deque()
  queue.append([start,''])
  visited=set()
  visited.add(start)
  op=['*','+','/']

  while queue:

    node,oper=queue.popleft()
    if node==ti:
      print(oper)
      return


    for t in op:

      if t=='+':
        temp=node+node
        if temp not in visited and 0<=temp<=10**9:
          visited.add(temp)
          queue.append([temp,oper+'+'])
      elif t=='*':
        temp=node*node
        if temp not in visited and 0<=temp<=10**9:
          visited.add(temp)
          queue.append([temp,oper+'*'])
      elif t=='/':
        temp=node//node
        if temp not in visited:
          visited.add(temp)
          queue.append([temp,oper+'/'])

  print(-1)
  return

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

if s==ti:
  print(0)
else:
  bfs(s)