[백준] 소수 경로

접근 방법 : 에라토스테네스의 체, BFS, 문자열 슬라이싱

에라토스테네스...소수 나오면 바로 써먹어야겠다.
오랜만에 풀어서 그런지 BFS 응용문제 나오면 감을 못잡겠다.
문자열 슬라이싱도 간만에 해서 기억이 잘 안났다.

import sys
from collections import deque

T = int(sys.stdin.readline())

primes = [False, False] + [True] * (9999)
result = []

for i in range(2, 10000):
    for j in range(2*i , 10000, i):
        primes[j] = False

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

    que = deque([])
    que.append([start, 0])

    visited = [False] * 10000

    while que:
        cur, cnt = que.popleft()
        visited[cur] = True

        if cur == end:
            result.append(cnt)
            break

        temp = str(cur)

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

                if not visited[next] and primes[next] and next >= 1000:
                    que.append([next, cnt + 1])
    
    else:
        result.append(-1)

for r in result:
    if r == -1:
        print("impossible")
    else:
        print(r)