파이썬)

 

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

 

 

import sys, math
from collections import deque

def findPrime():
    # 에라토스테네스의 체(제곱근 범위까지 조사)
    for i in range(2, 100):
        # 소수인 상태에서 소수의 배수를 체크해줘야 함
        if prime[i] == True:
            # 소수의 배수 체크
            for j in range(2*i, 10000, i):
                prime[j] = False

def bfs():
    q = deque()
    q.append([start, 0])

    visited = [0 for i in range(10000)]
    visited[start] = 1

    while q:
        now, cnt = q.popleft()
        strNow = str(now)

        if now == end:
            return cnt

        for i in range(4):
            for j in range(10):
                temp = int(strNow[:i] + str(j) + strNow[i+1:])

                if visited[temp] == 0 and prime[temp] and temp >= 1000:
                    visited[temp] = 1
                    q.append([temp, cnt + 1])


t = int(sys.stdin.readline())
prime = [True for _ in range(10000)]
findPrime()

for _ in range(t):
    start, end = map(int, sys.stdin.readline().split())

    result = bfs()
    print(result if result != None else "Impossible" )