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

문제 링크 : https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 

에라토스테네스의 체랑 BFS를 사용하면 어렵지 않게 풀 수 있는 문제이다.

출발 숫자에서 한번에 한자리씩 바꾸면서 목표 숫자까지 도달해야하는데 이때 중간에 만들어지는 모든 숫자도 소수여야한다.

테스트케이스 개수까지 입력받으므로 미리 9999까지 소수를 찾아 놓고 테스트케이스를 시작하자.

각 자리 숫자 바꾸는 건 문자열 슬라이싱으로 바꾸고 이를 형변환해서 사용했다.

 

from sys import stdin
from collections import deque

input = stdin.readline

tc = int(input())

prim_num = [True]*10000
visited = [0]*10000
visited_num = 0
def set_prime():
    global prim_num
    for i in range(2,100):
        if prim_num[i]:
            for j in range(i+i,10000,i):
                prim_num[j] = False
def solv():
    a,b = input().strip().split()

    q = deque([(a,0)])
    visited[int(a)] = visited_num

    while q:
        now,cnt = q.pop()
        if now == b:
            print(cnt)
            return

        for idx in range(4):
            for num in range(0,10):
                if idx == 0 and num == 0:
                    continue
                new_num = now[:idx]+str(num)+now[idx+1:]
                int_new_num = int(new_num)
                if prim_num[int_new_num] and visited[int_new_num] != visited_num:
                    visited[int_new_num] = visited_num
                    q.appendleft((new_num,cnt+1))

    print('Impossible')

set_prime()
for _ in range(tc):
    visited_num += 1
    solv()