[백준] 1963번 소수 경로 - 파이썬 (Python)

문제 (링크)

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

1963번: 소수 경로

 

나의 풀이

from collections import deque
import sys

def get_prime_nums():
    prime = [True] * 10000
    prime[0], prime[1] = False, False
    
    for i in range(2, 10000):
        if prime[i] == True:
            j = 2

            while i * j < 10000:
                prime[i * j] = False
                j += 1

    return prime

def bfs(start, target):
    q = deque()
    # 시작점과 카운트
    q.append([start, 0])
    visited = [False] * 10000
    visited[start] = True

    while q:
        current, cnt = q.popleft()

        if current == target:
            return cnt
        
        current = str(current)

        for i in range(4):
            for j in range(10):
                temp = int(current[:i] + str(j) + current[i+1:])

                if not visited[temp] and prime_nums[temp] and temp >= 1000:
                    visited[temp] = True
                    q.append([temp, cnt+1])
    # 불가능
    return None

if __name__ == "__main__":
    n = int(input())
    prime_nums = get_prime_nums()
    ans = []
    for _ in range(n):
        start, target = map(int, input().split())
        ans.append(bfs(start, target))

    for x in ans:
        if x == None:
            print("Impossible")
        
        else:
            print(x)

코드 설명 및 풀이법

에라토스테네스의 체와 BFS를 함께 사용하여 풀 수 있는 문제였다.

 

먼저, 에라토스테네스의 체를 이용해 네 자리 수 중 존재하는 모든 소수들을 구해준다.

 

이후, 현재 숫자(start)에서 출발해 각 자리수에 0부터 9까지 하나씩 넣어보며 소수이면서 1000 이상의 숫자들에 대한 BFS를 진행해준다.