백준 1963 파이썬 - 소수경로

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

1963번: 소수 경로

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

코드

import sys
from collections import deque
t = int(sys.stdin.readline())
prime = [list(map(int, sys.stdin.readline().split())) for _ in range(t)]
arr = [True] * 10001
for i in range(2, 101):
    if arr[i]:
        j = i * 2
        while j < 10001:
            arr[j] = False
            j += i
def bfs(a, b):
    q = deque()
    q.append((a, 0))
    visited = [0 for _ in range(10000)]
    visited[a] = 1
    while q:
        num, cnt = q.popleft()
        if num == b:
            return cnt
        if num < 1000:
            continue
        for i in [1, 10, 100, 1000]:
            n = num - num % (i * 10) // i * i
            for j in range(10):
                if visited[n] == 0 and arr[n]:
                    visited[n] = 1
                    q.append((n, cnt + 1))
                n += i
    return "impossible"
for i, j in prime:
    print(bfs(i, j))

풀이

소수는 에라토스테네스의 체로 배열에 소수인지 불리안 타입으로 저장하고, 1의자리수부터 1000의자리수까지 바꿔보면서 BFS를 돌리면 된다.