[맛있는물회] [파이썬] <백준 알고리즘> 1963번 "소수 경로"

문제 조건

---

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

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

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

 

Input

---

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

 

Output

---

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

 

생각한 아이디어

---

코드가 쫌 더럽다....

일단 prime을 구하는 방법은 에라토스테네스의 체를 이용하여 10000까지 구하였다.

 

그 이후 나는 bfs를 사용하면서 이중포문을 이용하였다.

pos를 통해 각 자리수에 위치시키고, 반복문을 통해 0~9까지로 변경했다.

그리고 prime 체크를 해주고, 만약 이전에 체크했던 값 즉, visited안에 있다면 바로 횟수를 넣지않고, 이전의 값과 비교해서 이전의 값보다 작을때만 queue에 넣어주었다.

 

사실 시간복잡도가 꽤 큰 것 같아서 돌아갈까 걱정은 했지만 잘 돌아갔따.

 

BFS 코드를 좀 다음어야겠따.

 

소스코드

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

def make():
   check=[False,False]+[True]*9999
   prime=[]
   for i in range(2,10000):
      if check[i]:
         prime.append(i)
         idx=i*2
         while 10000>idx:
            if check[idx]==True: 
               check[idx]=False
            idx +=i
   return prime

def bfs(start,end,prime):
   queue=deque()
   queue.append(start)
   visited= [start]
   check =[0 for _ in range(10001)]

   while queue:
      val = queue.popleft()
      if val==end:
         return check[val]
      for pos in range(0,4):
         for i in range(0,10):
            tmp = int(str(val)[:i] + str(i) + str(val)[i+1:])
            
            if tmp in prime:
               if tmp in visited:
                  if check[tmp]>check[val]+1:
                     check[tmp]=check[val]+1
                     queue.append(tmp)
                     visited.append(tmp)
               else:
                  check[tmp]=check[val]+1
                  queue.append(tmp)
                  visited.append(tmp)

if __name__ == "__main__":
   t=int(input())
   for _ in range(t):
      a,b=map(int,input().split())
      prime = make()
      print(bfs(a,b,prime))

 

*파이썬 문법 정리