[백준] 1963번 : 소수경로

1963번: 소수 경로

1963번: 소수 경로

🤔 문제분석

모든 숫자를 대입해보면서(완전탐색) 소수이고 방문하지 않는 소수만 방문해(너비우선탐색)나아가면서 문제를 해결하면 된다. 4자리 숫자이기 때문에 시간내에 문제를 해결 할 수 있습니다.

• 참고 : 소수를 판별하는 방법은 제곱근의 수 + 1 만큼만 비교하면 된다. (에라토스테네스의 체)

💻 코드

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

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

for _ in range(int(input())):
    num1, num2 = map(int, input().split())
    visited = set([num1])
    queue = deque()
    queue.append((num1, 0))
    while queue:
        num, cost = queue.popleft()
        if num == num2:
            print(cost)
            
        for n in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
            for i in range(4):
                temp = list(str(num))
                if temp[i] != str(n):
                    temp[i] = str(n)
                    new_number = int(''.join(temp))
                    if new_number >= 1000 and is_prime(new_number):
                        if not new_number in visited:
                            visited.add(new_number)
                            queue.append((new_number, cost + 1))