[BOJ/Python] 1963_소수 경로

문제 출처: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

---

풀이

 

네 자리 소수에 대하여 소수 A -> 소수 B로 변환할 때 필요한 최소 횟수를 출력하는 문제이다.

변환할 때 필요한 조건은 다음과 같다.

• 변환하는 과정에도 항상 네 자리 소수임을 유지하여야 한다.
• 변환의 경우, 해당 소수의 일의 자리, 십의 자리, 백의 자리, 천의 자리 수를 다른 수로 바꿀 수 있다.
• 이 경우, 바꾸는 수 또한 소수여야 한다.
• 최종적으로 변환할 때 필요한 최소 횟수를 출력하며, 불가능 할 경우 Impossible을 출력한다.

코드는 다음과 같다.

 

import sys
import collections
 
def change_num(num):
    change_list = []
    for i in range(1,10):
        num1 = (i*1000+num%1000)
        if num1 != num:
            if num1 in prime_numbers:
                if num1 not in visited:
                    visited.add(num1)
                    change_list.append(num1)
 
    for i in range(10):
        num2 = (num//1000)*1000 + i*100 + num%100
        num3 = (num//100)*100 + i*10 + num%10
        num4 = (num//10)*10 + i
 
        if num2!=num:
            if num2 in prime_numbers:
                if num2 not in visited:
                    visited.add(num2)
                    change_list.append(num2)
        if num3!=num:
            if num3 in prime_numbers:
                if num3 not in visited:
                    visited.add(num3)
                    change_list.append(num3)
        if num4!=num:
            if num4 in prime_numbers:
                if num4 not in visited:
                    visited.add(num4)
                    change_list.append(num4)
 
    return change_list
 
def bfs(start,end):
    queue = collections.deque()
    queue.append(start)
    count = 1
    result = 0
 
    while queue:
        num = queue.popleft()
        if num==end:
            return result
        count-=1
        queue.extend(change_num(num))
        if count==0:
            count = len(queue)
            result+=1
 
    return "Impossible"
 
nums = [True for _ in range(10000)]
for i in range(3,1000,2):
    if nums[i]:
        for j in range(i,10000,i):
            nums[j]=False
 
prime_numbers=set()
for i in range(1001,10000,2):
    if nums[i]:
        prime_numbers.add(i)
        for j in range(i,10000,i):
            nums[j]=False
            
t = int(sys.stdin.readline())
for _ in range(t):
    visited=set()
    start, end = map(int,sys.stdin.readline().split())
    if start==end:
        print(0)
    else:
        print(bfs(start,end))

• 현재 수 num (4자리 소수)를 기준으로 하여, 변환을 수행하는 함수이다.
• num1, num2, num3, num4의 경우 각각 천의 자리, 백의 자리, 십의 자리, 일의 자리를 변환한 수이다.
• 만약 변환한 수가 현재 수와 같을 경우 변환하는 의미가 없으므로 생략한다. (num1==num 일 경우이다.)
• 만약 변환한 수가 현재 수와 동일하지 않다면, 해당 수가 소수인지 확인한다.
• 만약 소수가 맞다면 이미 방문한 소수인지 확인하고 아니라면 change_list에 넣어준다.
• 최종적으로 change_list를 반환하고, 이 change_list는 bfs 함수에서 큐에 extend 된다.

bfs 함수

• 큐를 이용하여 구현한다.
• 큐에 원소가 존재하는 동안 반복하며, 큐에 원소를 하나씩 꺼내어 바꾸려는 소수인지 확인한다.
• 바꾸려는 소수가 아니라면 change_num 함수를 수행하여 해당 소수를 기준으로 새로운 소수들을 생성하고 큐에 넣어준다.
• count와 result를 이용하여 소수를 변환하는 횟수를 세고, 최종적으로 바꾸려는 소수가 나타나면 result를 return 한다.
• 만약 큐에 원소가 더 이상 존재하지 않으며 바꾸려는 소수를 찾지 못했다면 불가능하므로 Impossible을 return 한다.