[백준] 1963번 소수 경로

💡문제접근

• 에라토스테네스의 체를 이용한 소수 판정 알고리즘과 BFS 완전 탐색을 이용한 문제였다.
• 로직은 떠올렸으나 코드로 옮기는 과정에서 시간이 소요됐던 문제였다. 꾸준한 연습이 필요해보인다.

💡코드(메모리 : 34176KB, 시간 : 168ms)

from collections import deque
import sys
input = sys.stdin.readline

def BFS(A, B):
    global arr
    queue = deque()
    queue.append(A)
    visited[A] = True
    while queue:
        a = queue.popleft()
        if a == B:
            print(arr[a])
            return
        a = str(a)
        for i in range(4):
            for j in range(10):
                val = int(a[:i] + str(j) + a[i+1:])
                # 4자리 수이면서 소수여야 한다.(방문하지 않은 숫자의 경우만 탐색)
                if 1000 <= val <= 9999 and not visited[val] and arr[val] == 0:
                    arr[val] = arr[int(a)] + 1
                    visited[val] = True
                    queue.append(val)

T = int(input())
for _ in range(T):
    visited = [False] * 10001
    arr = [0] * 10001
    for i in range(2, 101):
        for j in range(2*i, 10001, i):
            arr[j] = 1
    A, B = map(int, input().strip().split())
    BFS(A, B)

💡소요시간 : 37m