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

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

1963번: 소수 경로

풀이

시작값과 목표값이 각 테스트케이스마다 주어진다.

시작값의 각 자리의 숫자를 바꿔가면서 소수를 유지하면서 목표값으로 바꿀 수 있는가?

1, 에라토스테네스의 체 알고리즘으로 1000 ~ 9999까지의 숫자들 중 소수만 뽑아서 리스트를 만들어준다.2, BFS를 실행해서 숫자의 각 자리를 1~9까지의 숫자로 바꿔가면서 목표값까지 이동할 수 있나 없나 확인한다.대신 첫방문이며 소수여야하고 1000이상인 숫자여야한다.(숫자의 앞자리가 0인경우만 제외하면 모두 4자리이기에) 3, visited에 몇 개의 소수를 거쳐왔는지 저장해준다. 시작값의 visited값을 1로 해놨기 때문에 출력할때는 1을 빼준다. 

 

# 1963번 소수 경로
# 숫자를 바꾸는 과정에서도 네자리숫자임을 유시해야하며 소수여야한다.
from collections import deque

# 에라토스테네스의 체 알고리즘
def prime(list):
    for i in range(2, 100):
        if list[i]:
            for j in range(i*2, 10000, i):
                list[j] = False
    return list

def bfs(prime, start, end):
    queue = deque()
    queue.append(start)
    visited = [0] * 10000
    visited[start] = 1
    while queue:
        x = queue.popleft()
        str_x = str(x)
        if x == end:
            return visited[x]
        for i in range(4):
            for j in range(10):
                nx = int(str_x[:i] + str(j) + str_x[i+1:])
                if prime[nx] == True and visited[nx] == 0 and nx >= 1000:
                    visited[nx] = visited[x] + 1
                    queue.append(nx)
    return "Impossible"

def solve():
    arr = [True for _ in range(10000)]
    prime_li = prime(arr)
    N = int(input())
    for _ in range(N):
        a, b = map(int, input().split())
        print(bfs(prime_li, a, b)-1)

solve()

출력결과