[백준] 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

 

---

난이도 : 골드4 

풀이 - 에라토스테네스의 체 + bfs 

 

모든 경우의 수를 전부 찾아야 하는 완전 탐색이면서 bfs를 사용한 문제이다.

네 자리 수인 9999까지의 모든 수를 에라토스테네스의 체를 이용해서 소수인지 판별을 한다.

그 다음은 bfs를 사용하여 각 자리 수마다 숫자(0~9)를 넣어가며 소수인 수는 큐에 다시 넣어서 또 다시 자릿수를 바꾸어 가며 바껴야 하는 숫자가 나올 때까지 판별한다.

 

다른 분의 코드를 보며 풀었는데 각 자리에 숫자를 넣는 부분을 문자열로 변환해서 바꿀 생각을 못했어서 하나 또 배웠다.

 

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

def isPrime(num):
    if num == 1:
        return False
    for i in range(2, int(num **0.5)+1):
        if num % i == 0:
            return False
    return True

def bfs(A,B):
    q = deque()
    q.append((A,0))
    while q:
        password, count = q.popleft()
        if password == B:
            return count
        for i in range(4):
            # 각 자리에 0 ~ 9를 넣어가며 소수인지 확인
            for j in range(10):
                new_pass = list(str(password))
                new_pass[i] = str(j)
                new_pass = int(''.join(new_pass))      
                # 1000 이상, 방문 x, 소수 o        
                if 1000 <= new_pass and not visited[new_pass] and isPrime(new_pass):
                    visited[new_pass] = 1
                    q.append((new_pass, count+1))
    
T = int(input())
#소수 판별
prime = [False]
for i in range(1,10000):
    prime.append(isPrime(i))

#테스트 케이스
for _ in range(T):
    A, B = map(int,input().split())
    visited = [0] * 10000
    visited[A] = 1
    result = bfs(A,B)
    print(result if result != None else "Impossible")