문제

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

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

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

www.acmicpc.net/problem/1963

  • 입력

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

  • 출력

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

최종코드

일단 4자리수 소수를 전부 구해놓고 원래 숫자 a에서 숫자를 한 자리씩 바꿔가면서 푸는 방법까진 생각했다. 근데 구현에서 완전히 막혀버렸다. 왤케 어려운지ㅜ. 분발하자!!

숫자를 한 자리씩 바꾸는 방법에는 여러가지가 있었는데 숫자를 문자열로 바꿔서 합치는 방법이 제일 간편해보여서 그렇게 구현했다.

import sys
from collections import deque

def check(): # bfs
    global a, b, prime
    q = deque()
    q.append([a, 0])
    visit = [False]*10000
    visit[a] = True

    while q:
        # now: 현재 숫자, cnt: 바꾼 횟수
        now, cnt = q.popleft()
        # 숫자를 문자열로 변환
        strNow = str(now)
        # 현재 숫자가 바꾸려는 숫자와 일치하면 return cnt
        if now == b:
            return cnt

        # 1부터 4까지 한 자리씩 탐색
        for i in range(4):
            # 0부터 9까지 바꿔가면서 넣어본다
            for j in range(10):
                temp = int(strNow[:i] + str(j) + strNow[i+1:])
                # 아직 방문하지 않은 숫자이고, 소수이며, 4자리수인 경우 bfs
                if visit[temp] == False and prime[temp] and temp >= 1000:
                    q.append([temp, cnt+1])
                    visit[temp] = True
    # 바꾸려는 수에 도달하지 못한 경우
    return "IMPOSSIBLE"


t = int(sys.stdin.readline())

# 4자리수 소수 구하기
prime = [True]*10000
prime[0] = prime[1] = False
for i in range(2, int(10000**0.5)):
    if prime[i] == True:
        for j in range(i*2, 10000, i):
            prime[j] = False

while t:
    a, b = map(int, sys.stdin.readline().split())
    print(check())
    t -= 1

참고 사이트