백준 1963 소수경로

gmlwlswldbs·2021년 10월 28일
0

코딩테스트

목록 보기
65/130
from collections import deque

p = [-1, -1] + [0] * 9998
prime = []
for i in range(2, 10000):
    if p[i] == 0:
        prime.append(i)
    for j in range(2*i, 10000, i):
        p[j] = -1

def sosu(a, b):
    check = [-1] * 10000
    q = deque()
    q.append(a)
    check[a] = 0
    while q:
        x = q.popleft()
        if x == b:
            return check[b]
        u = int(x/1000)
        v = int(x/100)-(10*u)
        z = x % 10
        w = int((x%100 - z)/10)
        y_list = []
        for i in range(1, 10):
            y_list.append(i*1000 + v*100 + w*10 + z*1)
        for i in range(0, 10):
            y_list.append(u*1000 + i*100 + w*10 + z*1)
            y_list.append(u*1000 + v*100 + i*10 + z*1)
            y_list.append(u*1000 + v*100 + w*10 + i*1)
        for y in y_list:
            if check[y] == -1 and (y in prime):
                q.append(y)
                check[y] = check[x] + 1
    return check[b]

t = int(input())

for test_case in range(t):
    a, b = map(int, input().split())
    ans = sosu(a, b)
    if ans == -1:
        print('Impossible')
    else:
        print(ans)

에라토스테네스 체로 소수를 모두 구한 후 -> 한자리씩 1-9 또는 0-9 를 바꿔 넣어서 bfs

0개의 댓글