소수 경로 (백준 1963번)

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

1963번: 소수 경로

언제나 문제를 풀면서 느끼지만 스토리가 참 재밌는 경우가 많다. 비밀번호를 소수로 정하는 친구가 있다는게...

 

여하튼, 이 문제는 시작 소수와 도착 소수가 쌍으로 주어진다. 시작 소수에서 한 자리씩 바꿔가며 도착 소수로 변경하고자 할 때, 걸리는 최소 과정을 출력하는 문제이다.

 

예를 들어 1033에서 8179로 가기 위해서는 1033 1733 3733 3739 3779 8779 8179 처럼 총 6번의 과정이 필요하다.

---

이 문제의 경우 테스트 케이스가 여러번 있고 입력은 항상 네자리 소수만 주어지므로 9999까지 에라토스테네스의 체를 사용해서 소수를 구해두고 매 테스트 케이스마다 사용해야한다.

prime = [i for i in range(0, 10001)]

def seive():
    for i in range(2, 5000):
        if prime[i] != 0:
            for j in range(i+i, 10000, i):
                prime[j] = 0

 

로직은 간단하다. 최소 변환 수를 찾아야 하므로 입력받은 시작 소수에서, 1000의 자리부터 한 자리씩 올려가면서 그 수가 소수임을 판별하고, 만약 소수라면 변환 횟수를 한 자리 올려준후 큐에 집어 넣고 bfs를 하면 된다.

 

한 자리씩 숫자를 변경하는 과정이 조금 복잡할 수 있는데, 문자열 concat을 이용하면 쉽게 해결할 수 있다.

예를 들어, 1033의 경우, 천 자리수를 바꿔주고 싶다면 , ' ' + '0' ~ '9' + '033' 이렇게 반복해주면(천의 자리의 경우 맨 앞에는 0이 올 수 없다.) 1033부터 9033까지 숫자를 만들 수 있다.

백의 자리인 경우 '1' + '0' ~ '9' + '33' 이러면 1033 부터 1933 까지 숫자를 만들 수 있다.

 

전체 코드

import sys
from collections import deque

prime = [i for i in range(0, 10001)]

def seive():
    for i in range(2, 5000):
        if prime[i] != 0:
            for j in range(i+i, 10000, i):
                prime[j] = 0

def bfs(st, en):
    q = deque()
    q.append((st, 0))
    while q:
        c, cnt = q.popleft()
            return cnt
        str_c = str(c)
        cnt += 1
        for i in range(4):
            for j in range(10):
                j = str(j)
                # 1000자리 수는 0이어선 안된다.
                if i == 0 and j == '0':
                    continue
                num = int(str_c[:i] + j + str_c[i+1:])
                if prime[num] and not visited[num]:
                    visited[num] = True
                    q.append((num, cnt))
    return 'Impossible'

# 소수 테이블 세팅
seive()

t = int(sys.stdin.readline())
for _ in range(t):
    st, en = map(int, sys.stdin.readline().split())
    visited = [False] * 10001
    print(bfs(st, en))

---

에라토스테네스의 체에 대한 설명은 여기서 해두었다.

https://k1ng-dev.tistory.com/68

에라토스테네스의 체