[백준 1963 : PYTHON] 소수 경로

문제 풀기 : 1963번

1963번: 소수 경로

문제

입력은 항상 네 자리 소수만(1000 이상) 주어지며 주어진 두 소수 A에서 B로 바꾸는데 필요한 최소 단계를 구한다.

바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 한다.

문제풀이

모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다.

우선 네 자리 수인 9999까지의 모든 수를 완전탐색을 통해서 소수인지 판별을 한다.

그 다음은 각 자리수마다 숫자(0 ~ 9)를 바꾸어 가며 소수인 수는 큐에 넣어서 또 다시 자릿수를 바꾸어 가며 바꾸어야 하는 숫자가 나올 때 판별한다.

이 때 다음과 같은 조건을 생각해야 한다.

1. 큐에 넣은 숫자는 방문 처리를 한다. (visited) - 카운트 중복 방지
2. 과정 중에는 네 자리 숫자를 유지해야 하므로 바꾼 숫자가 1000이상인지 확인한다.

코드 TIP

소수를 구하는 방법

• 에라토스테네스의 체

  소수인지 판별하고자 하는 숫자의 제곱근 내에 있는 수들의 배수를 걸러낸다.

  시간 복잡도는 O(n log log n)이다.

전체코드

import sys, math
from collections import deque

def findPrime():
    # 에라토스테네스의 체(제곱근 범위까지 조사)
    for i in range(2, 100):
        # 소수인 상태에서 소수의 배수를 체크해줘야 함
        if prime[i] == True:
            # 소수의 배수 체크
            for j in range(2*i, 10000, i):
                prime[j] = False

def bfs():
    q = deque()
    q.append([start, 0])

    # 방문여부
    visited = [0 for i in range(10000)]
    visited[start] = 1

    while q:
        now, cnt = q.popleft()
        # now를 숫자에서 문자로 변환
        strNow = str(now)

        # 빼낸 값이 end면 cnt 리턴 
        if now == end:
            return cnt

        for i in range(4):
            # 각 자리에 0 ~ 9를 넣어가며 소수인지 확인
            for j in range(10):
                temp = int(strNow[:i] + str(j) + strNow[i+1:])

                # 방문 X, 소수 O, 1000이상인 숫자
                if visited[temp] == 0 and prime[temp] and temp >= 1000:
                    visited[temp] = 1
                    q.append([temp, cnt + 1])


# 테스트 케이스 횟수
t = int(sys.stdin.readline())
# 소수 판별 배열
prime = [True for _ in range(10000)]
# 소수 판별
findPrime()

for _ in range(t):
    # 입력
    start, end = map(int, sys.stdin.readline().split())

    # start ~ end의 단계 카운트
    result = bfs()
    print(result if result != None else "Impossible" )