[백준][Python]14395번(4연산)

백준 14395번

✔️ 문제 풀이

◾ bfs 활용하는 간단한 문제

• 정말 연산에 따라 bfs 탐색만 진행하면 끝이다...
• visited를 단순 방문체크 용도로 사용하지 않고 지금까지의 연산을 저장하는 용도로 활용
• 수의 범위가 1 ~ 1000000000로 너무 광범위해서 visited를 배열로 선언하지 않고 딕셔너리로 선언함
• 연산결과가 visited의 키값으로 존재하지 않으면 방문한 적 없는 것이다
• 문제에서 연산우선순위(* ⇒ + ⇒ - ⇒ /)를 지정하고 있기 때문에 이 순서에 따라 연산 순서를 나열하고, 결과값을 출력하면 된다.

최종 제출 코드

from collections import deque

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

if s==t:
  print(0)

else:
  visited = dict()
  visited[s] = ''
  
  q = deque()
  q.append(s)
  
  while q:
  
    num = q.popleft()

    if num == t:
      break
      
    if num*num<=10**9 and num*num not in visited:
      visited[num*num] = visited[num]+'*'
      q.append(num*num)
    if num+num<=10**9 and num+num not in visited:
      visited[num+num] = visited[num]+'+'
      q.append(num+num)
    if 0 not in visited:
      visited[0] = visited[num]+'-'
      q.append(0)
    if num != 0 and 1 not in visited:
      visited[1] = visited[num]+'/'
      q.append(1)

  print(visited[t] if t in visited else -1)

✔️ 실행 결과