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

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

1963번: 소수 경로

다른 사람들의 풀이보다 시간복잡도가 뒤쳐지지만, TLE도 아니고 스스로 풀었으니까 만족한다 ㅋㅎ

 

우선 입력범위에 해당 하는 소수들은 모조리 골라준다.

그리고 bfs를 시작하여, 현재 기준이 되는 소수와 단 한자리만 다르면서 아직 방문하지 않은 '소수'를 큐에 넣고 탐색을 이어간다.

 

한마디로 소수 판정 + bfs 이다.

import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def primeNumber():
    for i  in range(2, 10000):
        if pNum[i]:
            if i >= 1000:
                primes.append(i)
            for j in range(2*i, 10000, i):
                pNum[j] = False
        
def game_rule(a,b):
    cnt=0
    a = str(a)
    b = str(b)
    for i in range(4):
        if a[i] != b[i]:
            cnt += 1
    if cnt == 1:
        return True
    return False

def bfs():
    q=deque()
    visited = [False] * 10000
    
    q.append([p1,0])
    visited[p1] = True
    
    while q:
        now,mov = q.popleft()
        
        if now == p2:
            return mov
        
        for next in primes:
            if not visited[next] and game_rule(now,next):
                q.append([next,mov+1])
                visited[next] = True
    
    return -1
if __name__ == "__main__":
    t = int(input())
    
    pNum = [False, False] + [True] * 9998
    primes=[]
    primeNumber()
    
    for _ in range(t):
        p1, p2 = map(int,input().split())
        res = bfs()
        if res == -1: print('Impossible')
        else : print(res)