BOJ 1963 소수 경로

https://www.acmicpc.net/problem/1963
시간 2초, 메모리 256MB
input :

• test case의 수 T
• 1쌍씩 네 자리 소수

output :

• 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력

조건 :

• 비밀번호를 한 번에 한 자리 밖에 못 바꾼다.
• 1033 8179
• 1033 1733 3733 3739 3779 8779 8179

---

... 당연히 시간 초과 날 줄 알고 pypy로 냈는데 맞았다 개 꿀.....
1 ~ 10000 까지의 소수를 구한 후에.
1000 ~ 10000 사이의 숫자들을 저장해두고,
이 것들의 visit을 저장하도록 했다.

확인 해야 하는 경우가.
0번 쨰
1번 째
2번 째
3번 째 를 다 비교해야 하니 이를 조건문에 넣고 visit이 0일 때만 체크를 하자.

슬라이싱이 아닌 1, 10, 100, 1000으로 나눠서 체크를 하는것도 나쁘지 않을 것 같다.

import sys
from _collections import deque

t = int(sys.stdin.readline())

for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())
    prime_num = [1] * 10001
    prime_num[1] = 0
    number = []
    i = 2
    while i < 10001:
        cnt = i + i
        while cnt < 10001:
            prime_num[cnt] = 0
            cnt += i
        i += 1

    for i in range(1000, 10001):
        if prime_num[i] == 1:
            number.append(i)

    visit = [0] * len(number)
    q = deque([(n, 0)])

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

        if now == k:
            print(cnt)
            break

        now_str = str(now)
        for item in number:
            item_str = str(item)
            idx = number.index(item)
            if now_str[0] != item_str[0] and now_str[1:] == item_str[1:] and visit[idx] == 0:
                visit[idx] = 1
                q.append((item, cnt + 1))
            if now_str[0] == item_str[0] and now_str[1] != item_str[1] and now_str[2:] == item_str[2:] and visit[idx] == 0:
                visit[idx] = 1
                q.append((item, cnt + 1))
            if now_str[:2] == item_str[:2] and now_str[2] != item_str[2] and now_str[3] == item_str[3] and visit[idx] == 0:
                visit[idx] = 1
                q.append((item, cnt + 1))
            if now_str[:3] == item_str[:3] and now_str[3] != item_str[3] and visit[idx] == 0:
                visit[idx] = 1
                q.append((item, cnt + 1))

물론 좋은 코드는 아니다...