https://school.programmers.co.kr/learn/courses/30/lessons/154538
1) 최소 연산 횟수를 저장하는 리스트를 0으로 초기화한다.
2) x에서 y로 가는 최단 거리를 bfs로 구한다.
3) 이 때 x에서 n을 더하는 경우, 2를 곱하는 경우, 3을 곱하는 경우에 대해 분기를 쳐서 큐에 넣어준다
from collections import deque
def solution(x, y, n):
def bfs(x, y, n):
q = deque()
dist[x] = 1
q.append(x)
while q:
x = q.popleft()
if 0 <= x + n <= 1000000 and dist[x + n] == 0:
dist[x + n] = dist[x] + 1
q.append(x + n)
if 0 <= x * 2 <= 1000000 and dist[x * 2] == 0:
dist[x * 2] = dist[x] + 1
q.append(x * 2)
if 0 <= x * 3 <= 1000000 and dist[x * 3] == 0:
dist[x * 3] = dist[x] + 1
q.append(x * 3)
dist = [0] * 1000001
bfs(x,y,n)
return dist[y]-1
백준의 숨바꼭질과 매우 유사한 문제
https://www.acmicpc.net/problem/1697