2 minute read

1963번 : 소수 경로

문제 링크

https://www.acmicpc.net/problem/1963

문제 설명

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 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. 4자리 수의 모든 소수를 구한 배열을 저장
  2. 입력받은 수에서 1자리만 변경한 소수들을 확인했을 때 B로 변경가능하면 깊이 출력
  3. B로 아직 변경 못하면 1자리만 변경 가능한 소수들을 모두 BFS에 넣기
from collections import deque
import sys
input = sys.stdin.readline

# 4자리 수 소수들의 배열을 리턴하는 함수
def get_prime_numbers() -> list:
    isPrime = [True for x in range(10000)]

    for i in range(2, 10000) :
        if isPrime[i] : 
            for i in range(i**2, 10000, i) :
                isPrime[i] = False
            
    primeNums = [i for i in range(1000, 10000) if isPrime[i]]
    
    return primeNums

# 입력받은 수에서 변환 가능한 소수들의 배열을 리턴하는 함수
def next_prime_numbers(n: int) -> list :
    inputNum = str(n)
    nextNums = []
    
    for num in primeNums :
        compNum = str(num)
        count = 0
        for i in range(4) :
            if inputNum[i] == compNum[i] :
                count += 1
        if count == 3 :
            nextNums.append(int(compNum))
            
    return nextNums

# BFS 진행
def bfs(a, depth) :
    deq = deque([[a, depth]])

    while deq or depth > 1061 : 
        a, depth = deq.popleft()
        visited[a] = True
        nextNums = next_prime_numbers(a)

        if B in nextNums :
            return depth

        for num in nextNums : 
            if not visited[num] : 
                deq.append([num, depth+1])
                visited[num] = True
                
    return 'impossible'
    
primeNums = get_prime_numbers()
T = int(input())
for _ in range(T) :
    visited = [False for _ in range(10001)]
    A, B = map(int, input().split())
    if A == B : 
        print(0)
    else : 
        print(bfs(A, 1))

Comments

You May Also Enjoy