📩 출처
문제
소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:
- “이제 슬슬 비번 바꿀 때도 됐잖아”
- “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
- “그럼 8179로 해”
- “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
- “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
- “귀찮아”
그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.
입력
첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.
출력
각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.
👉 생각
- 4자리 숫자가 한번에 1개의 자리수만 바껴야하고 바뀐 숫자는 소수여야 하는 조건을 잘 신경써야 한다!
- 먼저 4자리 숫자의 각 자리수를 +1 하거나 -1할 수 있도록 lst 배열을 만들어주낟.
- lst를 통해 바뀐 숫자가, 4자리 숫자이고, 소수이며, 이전과 1자리만 바꼈는지 체크를 하고 q에 넣어주면 된다.
- 각각의 체크하는 것은 따로 함수로 구현을 했다!
from collections import deque
import sys
def isPrime(num):
if num == 1:
return False
for i in range(2, int(num**0.5)+1):
if not num % i:
return False
return True
def check(num1, num2):
num1, num2 = str(num1), str(num2)
cnt = 0
for i in range(4):
if num1[i] != num2[i]:
cnt += 1
return True if cnt == 1 else False
def bfs(start):
q = deque([])
q.append((start, 0))
visited = [0] * 9000
visited[start-1000] = 1
lst = list(range(1, 10)) + list(range(10, 100, 10)) + list(range(100, 1000, 100)) + list(range(1000, 10000, 1000)) + list(range(-1, -10, -1)) + list(range(-10, -100, -10)) + list(range(-100, -1000, -100)) + list(range(-1000, -10000, -1000))
while q:
current, cnt = q.popleft()
if current == end:
return cnt
for add in lst:
prime_number = current + add
if 1000 <= prime_number < 10000 and not visited[prime_number-1000] and isPrime(prime_number) and check(current, prime_number):
q.append((prime_number, cnt + 1))
visited[prime_number-1000] = 1
return "Impossible"
t = int(input())
for _ in range(t):
start, end = map(int, sys.stdin.readline().split())
print(bfs(start))
