[백준알고리즘] 1963번: 소수 경로 -Python

[백준알고리즘] 1963번: 소수 경로 -Python

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

1963번: 소수 경로

이번 문제 또한 특정 값 A, B가 주어지면 A에서 B까지 가는 최소 길이를 구하는 문제이다. 따라서 이번 문제도 DFS가 아닌 BFS를 사용해서 문제를 풀었다.

 

중복을 막기 위해서 visited라는 리스트를 추가로 사용했고, 소수들은 전처리로 구해놓았다.

 

큐를 이용한 BFS방식을 사용했으며 각 수에서 맨 앞자리가 0이 되지 않게 하면서 변경 가능한 소수들을 모두 구해서 큐에 추가해주었다.

 

import sys
from collections import deque

# set prime table
prime = [1] * 10001
for i in range(2, 5000):
    t = 2
    while i*t < 10000:
        prime[i*t] = 0
        t += 1

def bfs():
    queue = deque([(first, 0)])
    while queue:
        now, step = queue.popleft()
        if now == last:
            return step
        
        NOW = str(now)
        step += 1
        for i in range(4):
            for j in map(str, range(10)):
                if i == 0 and j == '0':
                    continue
                num = int(NOW[:i] + j + NOW[i+1:])
                if prime[num] and not visited[num]:
                    visited[num] = 1
                    queue.append((num, step))

for _ in range(int(sys.stdin.readline())):
    first, last = map(int, sys.stdin.readline().split())
    visited = [0] * 10001
    print(bfs())

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다