[백준 14395번] 4연산 -python

문제 링크

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

14395번: 4연산

 

풀이 

- bfs 문제

- set()으로 방문 여부 확인 

- 연산자마다 우선 순위 고려하여 우선 순위가 높은 순서부터 큐에 삽입 

- 빼기 연산을 하게 되면 0이 되어 최종값을 만들 수 없으므로 고려하지 않아도 됨 

from collections import deque 

INF = int(10e9)

def bfs(s,t):

  check.add(s)

  q = deque()
  q.append((s,""))

  while q:
    num, result = q.popleft()
    
    # t와 같으면 결과 리턴 
    if num == t :
      return result 
      
    # 범위에 포함되고 방문한 적이 없으면 
    tmp = num*num
    if 0<= tmp <= INF and tmp not in check :
      q.append((tmp, result + "*"))
      check.add(tmp)
    
    tmp = num+num
    if 0<= tmp <= INF and tmp not in check :
      q.append((tmp, result + "+"))
      check.add(tmp)  
    
    # 나누기 연산하면 1이 됨 
    tmp = 1 
    if 1 not in check:
      q.append((tmp, result+"/"))
      check.add(1)

  return -1 

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

# 방문 여부 확인 
check = set()

if s == t :
  print(0)
else :
  print(bfs(s,t))