백준
백준 1963 소수 경로 (파이썬)
chldkato
2020. 2. 17. 01:28
https://www.acmicpc.net/problem/1963
1963번: 소수 경로
문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아.
www.acmicpc.net
1. 에라토스테네스의 체로 범위 안의 모든 소수를 구한다
2. 주어진 입력에서 각 자릿수의 값을 바꿔가면서 이동할 수 있도록 bfs안에 조건문을 설계
3. bfs로 소수인 값만 이동하면서 목표값에 도달하면 횟수를 출력
from collections import deque
import sys
input = sys.stdin.readline
tc = int(input())
def p_num():
for i in range(2, 100):
if a[i] == 1:
for j in range(2*i, 10000, i):
a[j] = 0
def bfs(x):
q.append(x)
c[x] = 1
while q:
x = q.popleft()
if x == y:
print(c[x]-1)
return
for i in range(10):
if i != 0:
nx = (x % 1000) + i * 1000
if a[nx] == 1 and c[nx] == 0:
c[nx] = c[x] + 1
q.append(nx)
nx = int(x/1000)*1000 + (x % 100) + i * 100
if a[nx] == 1 and c[nx] == 0:
c[nx] = c[x] + 1
q.append(nx)
nx = int(x/100)*100 + (x % 10) + i * 10
if a[nx] == 1 and c[nx] == 0:
c[nx] = c[x] +1
q.append(nx)
nx = int(x/10)*10 + i
if a[nx] == 1 and c[nx] == 0:
c[nx] = c[x] + 1
q.append(nx)
a = [1 for _ in range(10000)]
p_num()
while tc:
q = deque()
c = [0 for _ in range(10000)]
x, y = map(int, input().split())
bfs(x)
tc -= 1