📚 1963 - 소수 경로

소수 경로

이해

이 문제는 에라토스테네스의 체를 이용한 후, bfs를 이용하여 문제를 풀면된다.

파이썬에서는 문자열합칠 때는 +를 이용하면 쉽게 합칠 수 있다.
temp = int(strNow[:i] + str(j) + strNow[i + 1:])

다만, 이 문제에서 불가능한 경우 Impossible이 아닌 0으로 결과를 처리해야 한다.

소스

import sys
from collections import deque

read = sys.stdin.readline

t = int(read())

# 소수 구하기

decimal_number = [True] * 10000

def decimal_function():
    for i in range(2, 10000):
        if decimal_number[i]:
            for j in range(i + i, 10000, i):
                decimal_number[j] = False


decimal_function()


def bfs():
    queue = deque()
    queue.append((a, 0))
    visited = [False] * 10010

    while queue:
        now, cnt = queue.popleft()
        strNow = str(now)

        if now == b:
            return cnt

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

                if not visited[temp] and decimal_number[temp] and temp >= 1000:
                    visited[temp] = True
                    queue.append((temp, cnt + 1))


while t > 0:
    a, b = map(int, read().split())
    result = bfs()
    if not result:
        print(0) # Impossible
    else:
        print(result)

    t -= 1

채점 결과