[BOJ] 1963 / 소수 경로 / Python 파이썬

[BOJ] 1963 / 소수 경로 / Python 파이썬

[BOJ] 1963 / 소수 경로 / Python 파이썬

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

1963번: 소수 경로

 

풀이

[BOJ] 1963 / 숨바꼭질 문제와 유사한 문제였다.

BFS 로 완전탐색을 하면서 memoization 으로 중복 탐색하는 경우를 제거하여 풀이하였다.

 

소수 판단은 "에라토스테네스의 체" 로 미리 만들어 주었고,

새롭게 생성되는 비밀번호는 자리수별로 0~9까지 변경하여 만들어 주었다.

 

 

from collections import deque

# 에라토스테네스의 체
def makePrime():
    nums = [1] * 10000
    nums[0] = 0
    nums[1] = 0

    for i in range(2, 10000):
        if nums[i]:
            for j in range(i, 10000, i):
                if i == j:
                    continue
                nums[j] = 0
    return nums


primes = makePrime()
case = int(input())

for _ in range(case):
    A, B = map(int, input().split())
    if A == B:
        print(0)
        continue
    if A > B:
        A, B = B, A

    queue = deque()
    queue.append(A)

    check = [0] * 10000
    check[A] = 1

    while True:
        Q = queue.popleft()

        if Q == B:
            print(check[Q]-1)
            break
		
        # 자리수
        for i in range(4):
        	# 변경 숫자 0~9
            for j in range(10):
                if i == 0 and j == 0:
                    continue
                nextQ = list(str(Q))
                nextQ[i] = str(j)
                nextQ = int("".join(nextQ))
				
                # 가능한 비밀번호 조건
                if primes[nextQ] and not check[nextQ]:
                    check[nextQ] = check[Q] + 1
                    queue.append(nextQ)