[백준/BOJ] gold4 - 1963번 소수 경로 (Python)

▶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을 출력한다.

728x90

▶풀이

소수를 알아야 하기에 이 부분은 에라토스테네스의 체를 이용했다.

사실, 소수 구하는 코드는 직접 짜기 귀찮아서 구글에 검색해서 가지고 왔다.

 

구현하고 싶은 사람은 아래 내용을 보고 구현하면 될 것이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

그 외에는 bfs()랑 다를 게 없었다.

 

그냥 숫자에서 한 자리씩 0 ~ 9까지 바꿔본다.

그 숫자가 소수인지 확인해 보고, 방문했는지 확인해 보고 조건에 맞다면 queue에 넣어준다.

 

bfs()를 잘 안다면 쉽게 풀 수 있는 문제였다.

소수를 구하는 건 뭐 이미 문제가 많이 있고, 구글링 해서 가져와도 될 것 같다.

from collections import deque

# 에라토스테네스의 체
def findPrime():
    for i in range(2, 100):
        if prime[i] == 0:
            for j in range(2 * i, 10000, i):
                prime[j] = 1


def bfs():
    queue = deque()
    queue.append((a, 0))

    visit = [0 for _ in range(10000)]
    visit[a] = 1

    while queue:
        num, cnt = queue.popleft()
        strnum = str(num)

        if num == b:
            return cnt
        
        for i in range(4):
            for j in range(10):
                tmp = int(strnum[:i] + str(j) + strnum[i + 1:])

                if visit[tmp] == 0 and prime[tmp] == 0 and tmp >= 1000:
                    visit[tmp] = 1
                    queue.append((tmp, cnt + 1))


t = int(input())
answer = []
prime = [0 for _ in range(10000)]

findPrime()
for _ in range(t):
    a, b = map(int, input().split())
    ans = bfs()
    if ans == None:
        answer.append('Impossible')
    else:
        answer.append(ans)

for ans in answer:
    print(ans)