🔥

문제

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

“이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데… 다음 소수를 무엇으로 할지 고민중이야” “그럼 8179로 해” “흠… 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데… 예를 들면… 1033 1733 3733 3739 3779 8779 8179처럼 말이야.” “흠…역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.” “귀찮아” 그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

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

출력

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

예제 1 입력

3
1033 8179
1373 8017
1033 1033

예제 1 출력

6
7
0

Source

from collections import deque

def getlist(x):
	arr = []
	# 천의 자리를 i로
	for i in range(1, 10):
		tmp = int(i * 1000 + x % 1000)
		if(tmp > 10000):
			continue
		if(isPrime[tmp] == 0 and x != tmp):
			arr.append(tmp)
	# 백의 자리를 i로
	for i in range(10):
		tmp = int((x / 1000)) * 1000 + i * 100 + x % 100
		if(tmp > 10000):
			continue
		if(isPrime[tmp] == 0 and x != tmp):
			arr.append(tmp)
	# 십의 자리를 i로
	for i in range(10):
		tmp = int((x / 100)) * 100 + i * 10 + x % 10
		if(tmp > 10000):
			continue
		if(isPrime[tmp] == 0 and x != tmp):
			arr.append(tmp)
	# 일의 자리를 i로
	for i in range(10):
		tmp = int((x / 10)) * 10 + i
		if(tmp > 10000):
			continue
		if(isPrime[tmp] == 0 and x != tmp):
			arr.append(tmp)

	return arr

isPrime = [0 for i in range(10001)]
# 에리토스테네스의 체
for i in range(2, 101):
	if(isPrime[i] == 1):
		continue
	for j in range(2*i, 10001, i):
		isPrime[j] = 1

t = int(input())
result = []

while(t > 0):
	t -= 1
	a, b = map(int, input().split())

	q = deque()
	dist = [0 for _ in range(10001)]

	q.append(a)
	dist[a] = 1
	while(len(q) != 0):
		x = q.popleft()
		for y in getlist(x):
			if(dist[y] == 0):
				dist[y] = dist[x] + 1
				q.append(y)
	if(dist[b] == 0):
		result.append("Impossible\n")
	else:
		result.append(dist[b] - 1)

for i in range(len(result)):
	print(result[i])

참고