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

 

1963번: 소수 경로

 

문제

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

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

 

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

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

 

예제 입력 3 1033 8179 1373 8017 1033 1033

예제 출력 6 7 0

 

풀이

 

BFS를 한 자리 수가 다른 소수끼리 진행하여 목표된 값을 찾는 문제이다.

에라토스테네스의 체로 10000 미만의 소수 리스트를 구한 뒤, BFS를 위한 큐에 담을 때 소수 리스트와 비교하여 해당 수가 소수인지 판별한다.

 

각각의 자리별로 만들 수 있는 수 리스트를 모두 구한 뒤 한 배열에 담고, 나중에 큐에 추가할 때 소수와 방문 여부를 검사하는 방식으로 구현했다.

 

from collections import deque
import sys
input = sys.stdin.readline

# 에라토스테네스의 체
prime = [True]*10001
for i in range(2,100):
    if prime[i]:
        prime[i*2::i] = [False]*((10000-i)//i)

for _ in range(int(input())):
    visit = [False]*10000
    start, end = map(int,input().split())
    q = deque([(start,0)])
    while q:
        n,cnt = q.popleft()
        if visit[n]:
            continue
        visit[n] = True
        
        if n == end:
            print(cnt)
            break
        
        nums = set()
        # 1000의 자리
        for i in range(1,10):
            nums.add(i*1000 + n%1000)
        # 나머지 자리
        for i in range(10):
            nums.add(i*100 + n//1000*1000 + n%100)
            nums.add(i*10 + n//100*100 + n%10)
            nums.add(n//10*10 + i)
            
        for i in nums:
            if not visit[i] and prime[i]:
                q.append((i,cnt+1))
    else:
        print("Impossible")