BOJ - 17394 - 핑거 스냅

import sys
from collections import deque

def BFS(arr, N, A, B):
    dq = deque()
    check = [False] * (1000000 + 1)
    check[N] = True
    dq.append((N, 0))
    
    while dq:
        v, w = dq.popleft()
        check[v] = True
        
        if arr[v] == True and A <= v <= B:
            return w
        
        if check[v//2] == False:
            dq.append((v // 2, w + 1))
            check[v//2] = True
        if check[v // 3] == False:
            dq.append((v // 3, w + 1))
            check[v//3] = True
        if v + 1 <= B * 4:
            if check[v + 1] == False:
                dq.append((v + 1, w + 1))
                check[v+1] = True
        if v - 1 >= 1:
            if check[v - 1] == False:
                dq.append((v - 1, w + 1))
                check[v-1] = True
    return -1

def solution():
    T = int(input())
    CHECK = [False, False] + [True] * (1000001)
    for i in range(2, 1000001):
        if CHECK[i]:
            for j in range(2 * i, 1000001, i):
                CHECK[j] = False

    for _ in range(T):
        N, A, B = map(int, sys.stdin.readline().split())
        print(BFS(CHECK, N, A, B))

solution()

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