백준 1963 소수 경로 (파이썬)

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

1963번: 소수 경로

1. 에라토스테네스의 체로 범위 안의 모든 소수를 구한다

2. 주어진 입력에서 각 자릿수의 값을 바꿔가면서 이동할 수 있도록 bfs안에 조건문을 설계

3. bfs로 소수인 값만 이동하면서 목표값에 도달하면 횟수를 출력

from collections import deque
import sys

input = sys.stdin.readline

tc = int(input())
def p_num():
    for i in range(2, 100):
        if a[i] == 1:
            for j in range(2*i, 10000, i):
                a[j] = 0

def bfs(x):
    q.append(x)
    c[x] = 1
    while q:
        x = q.popleft()
        if x == y:
            print(c[x]-1)
            return
        for i in range(10):
            if i != 0:
                nx = (x % 1000) + i * 1000
                if a[nx] == 1 and c[nx] == 0:
                    c[nx] = c[x] + 1
                    q.append(nx)
            nx = int(x/1000)*1000 + (x % 100) + i * 100
            if a[nx] == 1 and c[nx] == 0:
                c[nx] = c[x] + 1
                q.append(nx)
            nx = int(x/100)*100 + (x % 10) + i * 10
            if a[nx] == 1 and c[nx] == 0:
                c[nx] = c[x] +1
                q.append(nx)
            nx = int(x/10)*10 + i
            if a[nx] == 1 and c[nx] == 0:
                c[nx] = c[x] + 1
                q.append(nx)

a = [1 for _ in range(10000)]
p_num()
while tc:
    q = deque()
    c = [0 for _ in range(10000)]
    x, y = map(int, input().split())
    bfs(x)
    tc -= 1