문제

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

풀이

1. 10000까지의 숫자를 소수판별할 리스트와 방문처리 리스트를 만든다.
2. BFS 함수 안에서 각자리 숫자를 string 자료형을 이용해서 바꿔준다.
3. 방문했는지, 1000이상인지, 소수인지 검사함.
4. 검사에 통과하면 카운트 늘려가면서 B가 되면 카운트 리턴

모든 경우의 수가 소수경로가 있어서, Impossible 조건을 넣지 않아도됨. (깜빡하고 넣지 않았는데 정답처리되어 찾아봄)

from collections import deque
input = __import__('sys').stdin.readline

#소수판별함수
def isPrime(number):
    if number == 1:
        return False
    for i in range(2, int(number**1/2)+1):
        if number % i == 0:
            return False
    return True

#BFS
def bfs(A, B):
    q = deque()
    q.append((A,0))
    while q:
        password, count = q.popleft()
        if password == B:
            print(count)
            return
        for i in range(4):
            for j in range(10):
                new_pass = list(str(password))
                new_pass[i] = str(j)
                new_pass = int(''.join(new_pass))
                if 1000<=new_pass and not visited[new_pass] and prime[new_pass]:
                    visited[new_pass] = 1
                    q.append((new_pass, count+1))
                


#소수판별테이블
prime = [False]
for i in range(1,10000):
    prime.append(isPrime(i))

#테스트케이스
T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    visited = [0]*10000
    visited[A] = 1
    bfs(A,B)