1963: 소수 경로

풀이 시간

• 1h 2m

구현 방식

• 에라스토테네스의 체 알고리즘을 이용하여 10000 미만 소수를 판정할 수 있는 array를 미리 만듦
• bfs를 통해 4개의 자릿수 (일의 자리, 십의 자리, 백의 자리, 천의 자리) 마다 0 ~ 9까지 모든 경우를 확인하여 문제의 조건에 맞는 경우 해당 node를 queue에 추가
  -> 이 과정에서 자릿수를 처리해줄 때, string concatenation을 이용함
• 탐색의 depth가 두 소수 사이의 변환에 필요한 최소 회수임

코드

import sys
from collections import deque
import math


def bfs(src, dest):
    queue = deque([])
    queue.append((src, 0)) #수, 횟수
    visit = [False] * 10000
    visit[src] = True

    while queue:
        node, depth = queue.popleft()

        if node == dest:
            return depth

        str_node = str(node)
        for i in range(4):
            for j in range(10):
                nnode = int(str_node[:i] + str(j) + str_node[i+1:])
                if not visit[nnode] and array[nnode] and nnode >= 1000:
                    queue.append((nnode, depth+1))
                    visit[nnode] = True

    return "Impossible"

array = [True for i in range(10000+1)] #소수 배열
for i in range(2, int(math.sqrt(10000)) + 1):
    if array[i] == True:
        j = 2
        while i*j <= 10000:
            array[i*j] = False
            j += 1

T = int(sys.stdin.readline()[:-1])
for _ in range(T):
    src, dest = list(map(int, sys.stdin.readline()[:-1].split()))
    result = bfs(src, dest)
    print(result)

결과