백준(BOJ) 1963 소수 경로(Python)

문제 내용.

 

BFS 문제.

에라토스테네스의 체로 4자리 소수를 모두 담아두고, 입력받은 수에서부터 한 자리씩 바꾸면서 BFS를 진행한다.

한 수에서 체크해야하는 다음 경우는 모두 39가지이고, 그 중에서도 소수인 경우만 포함되므로 스택이 터지는 것에도 안전하다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

check=[0,0]+[1 for i in range(9998)]

for i in range(2,10000):
    if check[i]:
        for j in range(i*2,10000,i):
            check[j]=0

for _ in range(int(input())):
    queue=deque()
    a,b=map(int,input().split())
    visited=[0 for i in range(10000)]
    queue.append((a,0))
    visited[a]=1
    flag=0
    while queue:
        p,q=queue.popleft()
        if p==b:
            flag=1
            break
        for i in range(4):
            for j in range(10):
                if j==0 and i==0:
                    continue
                k=int(str(p)[:i]+str(j)+str(p)[i+1:])
                if check[k] and not visited[k]:
                    queue.append((k,q+1))
                    visited[k]=1
    if flag:
        print(q)
    else:
        print('Impossible')

아직 문제를 푸는 방법에 대한 확신이 없다.