[DFS] 이상한 계산기 - python

문제

입출력

💡 사고의 흐름

• 주어진 수 x에서 x*2, x//3을 하면서 경우를 체크하는 문제이므로 > DFS(너비우선탐색) 으로 풀어주어야 한다.
• DFS는 queue를 활용한다.
• q에 x, x*2, x//3을 집어 넣는다.
• 이때, check에는 counting 값을 넣어 check[x]가 x까지 총 몇 번 거쳐왔는지 기록하도록 한다.
• 이 문제는 주어진 조건에 다섯 자리 이상으로 넘어가면 안되게끔 작동하는 조건이 있어서 이 조건을 지켜주도록 if문 안에 조건을 달아준다.(이걸 놓쳐서 runtime error가 났었다^_^,,,)

Code

import sys
from collections import deque
n = int(sys.stdin.readline())
check = [0] *1000000

def cal(a, find):
  q = deque()
  q.append(a)
  check[a]=1
  while q:
    x = q.popleft()
    mul = x*2
    div = x//3
    if mul<1000000 and check[mul] ==0:
      q.append(mul)
      check[mul] =check[x]+1
      if find == mul: break
    if div<1000000 and check[div]==0:
      q.append(div)
      check[div] = check[x]+1
      if find == div: break
  return check[find]

if n==1 or n>999999:
  print(0)
else:
  print(cal(1,n)-1)