[백준 | 골드4] 1963: 소수경로(BFS, 에라토스테네스)

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

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 복사

3
1033 8179
1373 8017
1033 1033

예제 출력 1 복사

6
7
0

 

문제풀이

 

우선 네 자리 수인 9999까지의 모든 수를 완전탐색을 통해서 소수인지 판별을 한다.

-> 일일히 각각 소수를 만들지 않고, 처음 시작때 소수를 다 만들어놓고 시작한다.

각 자리수마다 숫자(0 ~ 9)를 바꾸어 가며 소수인 수는 큐에 넣어서 또 다시 자릿수를 바꾸어 가며 바꾸어야 하는 숫자가 나올 때 판별한다.

-. [0][1][2][3] 각각의 자리마다 0~9까지를 다 넣는다.

큐에 넣은 숫자는 방문 처리를 한다. (visited) 

-> 카운트 중복 방지

과정 중에는 네 자리 숫자를 유지해야 하므로 바꾼 숫자가 1000이상인지 확인한다.

from collections import deque
import sys
sys.stdin = open("20220911_1963_소수찾기.txt", "r")

#1부터 9999까지 소수를 먼저 찾는다
def isPrime(n) :
    board = [False, False] + [True] * (n - 1)
    primes = []

    for i in range(3, n+1) :
        if board[i] == True :
            primes.append(i)

        for j in range(i*2, n+1, i) :
            board[j] = False
    return primes

#소수인 경우 큐에 넣는다, 큐에 있는 4자리의 숫자는 각각 자리수 마다 0~9까지 바꾼다
#바꾼 수가 소수인 경우 다시 큐에 넣는다.
def BFS(start, target) :
    dq = deque()
    dq.append([start, 0])

    visited = [False] * (10000)
    visited[start] = True

    while dq :
        nowValue, count = dq.popleft()

        #각 자리수를 하나씩 뽑고 0부터 9까지 교체해보자
        strValue = list(str(nowValue))        #자리수 교체를 위해 문자열 -> 리스트 처리

        #목표 숫자에 도달하면 중지
        if nowValue == target :
            return count

        #[0][1][2][3] <-- 각 자리수에 0~9까지를 다 넣어본다. 
        for i in range(4) :
            copyValue = strValue[::]          #원본 숫자 유지를 위해 복사
            for j in range(10) :
                copyValue[i] = str(j)
                findValue = int("".join(copyValue))

                #기존에 만들지 않았었고, 1000보다 크고, 만든 숫자가 소수인 경우에 큐에 다시 넣기
                if visited[findValue] == False and 1000 <= findValue and findValue in primesList :
                    visited[findValue] = True
                    dq.append([findValue, count+1])

n = int(input())
primesList = isPrime(10000)

for i in range(n) :
    start, target = map(int, input().split())

    result = BFS(start, target)

    if result != None :
        print(result)
    else :
        print("Impossible")

#우선 네 자리 수인 9999까지의 모든 수를 완전탐색을 통해서 소수인지 판별을 한다.
#각 자리수마다 숫자(0 ~ 9)를 바꾸어 가며 소수인 수는 큐에 넣어서 또 다시 자릿수를 바꾸어 가며 바꾸어야 하는 숫자가 나올 때 판별한다.
#큐에 넣은 숫자는 방문 처리를 한다. (visited) - 카운트 중복 방지
# 과정 중에는 네 자리 숫자를 유지해야 하므로 바꾼 숫자가 1000이상인지 확인한다.