백준 1963번 소수 경로 (Python 3)

Baekjoon online judge 1963번 파이썬

 

링크

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

1963번: 소수 경로

에라토스테네의 체를 이용해 10000까지의 소수를 구한뒤, set으로 저장

bfs를 이용해서 입력된수의 천의자리~일의 자리까지 0~9로 바꾼다. 이때 천의 자리에는 1~9로 0으로 바꾸면 안된다는 것에 주의

 

큐에는 현재의 수와 현재의 수까지 오기위해 바꾼 횟수가 저장

큐에 담을 때 set을 이용한 소수 판정과 visited 판정

 

소스코드

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

def prime_list(n):
  # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
  sieve = [True] * n

  # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
  m = int(n ** 0.5)
  for i in range(2, m + 1):
    if sieve[i] == True:  # i가 소수인 경우
      for j in range(i + i, n, i):  # i이후 i의 배수들을 False 판정
        sieve[j] = False

  # 소수 목록 산출
  return [i for i in range(2, n) if sieve[i] == True]


prime=set(prime_list(10000))



for _ in range(int(input())):
  a,b=map(int,input().split())
  visited=set()
  visited.add(str(a))
  flag=True
  queue=deque()
  queue.append([str(a),0])
  thousand = [i for i in range(1, 10)]
  index = [i for i in range(0, 10)]

  while queue:
    node,cnt=queue.popleft()
    if node==str(b):
      print(cnt)
      flag=False
      break



    for t in thousand:
      new_node=str(t)+node[1:]
      if new_node not in visited and int(new_node) in prime:
        queue.append([new_node,cnt+1])
        visited.add(new_node)

    for i in range(1,4):
      for t in index:
        new_node=node[0:i]+str(t)+node[i+1:]
        if new_node not in visited and int(new_node) in prime:

          queue.append([new_node, cnt + 1])
          visited.add(new_node)
  if flag:
    print('Impossible')