[백준][Python]1963번(소수 경로)

백준 1963번

✔️ 문제 풀이

◾ 주어진 범위 내에서 소수를 먼저 구하고 시작

• 에라스토테네스의 체 활용

◾ bfs 활용

• 각각의 자리수의 값을 변경해가며 소수인지 아닌지 체크
• 소수이면서 방문한적 없는 숫자이면 dp 배열값을 변경해주고, 큐에 넣는다
• 팝된 수가 만들려고 했던 수와 일치하면 dp값 출력

최종 제출 코드

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

# 소수인 수 구하기
primes =[False, False]+[True]*9998
for i in range(2, int(len(primes)**0.5)+1):
  for j in range(i+i, len(primes), i):
    if not primes[i]: break
    primes[j] = False

# 반복횟수 입력받기
n = int(input().rstrip())

# 케이스별 반복
for i in range(n):
  start, end = map(int, input().split())
  
  lists = [10000]*10000
  lists[start] = 0
  
  q = deque()
  q.append(start)
  
  while q:
    number = q.popleft()
  
    if number == end:
      print(lists[number])
      break
      
    # 일의자리 수부터 천의자리 수까지 반복
    for i in range(4):
      # 0 ~ 9까지 반복
      for j in range(10):
        # 천의 자리 수가 0인 수는 4자리 수가 아니기 때문에 넘어간다
        if i==3 and j==0:
          continue
        # n번째 자리수를 변경한 수를 구한다
        new_num = number//(10**(i+1))*10**(i+1)+(10**i)*j+number%(10**i)
        # 계산 결과가 이번 순서에 팝한 수와 같을 경루 넘아간다
        if new_num == number:
          continue
        # 생성된 수가 소수이면서 방문한 적 없는 수이면 dp 배열값을 변경한다
        if lists[new_num] > lists[number] and primes[new_num]:
          lists[new_num] = lists[number]+1
          q.append(new_num)

✔️ 실행 결과