[BOJ] 1964. 소수 경로

문제

소수 경로 (https://www.acmicpc.net/problem/1963)

풀이

1. 초기접근

• 문제조건 해석
  • 한 step 단위로, 특정 수를 찾아야 하는 문제다.
    • BFS 문제다.
  • 현재 step에서 다음에 갈 step은 각 자릿수를 바꿔보며 소수인 경우다.
• 알고리즘
  • 먼저 어떤 수 i 가 소수인지 체크하는 배열을 미리 만든다.
    • 에라토스테네스의 체를 사용한다.
  • 현재 수의 각 자리를 0~9로 바꿔보며, 바꾼 수가 소수인 경우 큐에 넣어준다.
    • 그 외 조건들, 바꾼 수가 1000 보다 큰지, 바꾼 자릿수가 -1은 아닌지 등을 체크한다.
  • BFS를 이런 식으로 진행하다, 찾으려 했던 수를 찾으면 즉시 현재 step 을 반환한다.
• 코드

from collections import deque

def bfs(a, b):
    q, visited = deque([a]), set([a])
    step = 0

    while q:
        size = len(q)
        for _ in range(size):
            cur = q.popleft()

            if cur == b:
                return step

            # 현재 수에서 4개 자리의 수를 각각 0~10 으로 바꿔보며, 소수인 경우 큐에 넣는다.
            # 바꾼 자릿 수가 현재와 같은 수거나, 0 미만인 경우 제외.
            for d in range(4):
                for m in range(10):
                    str_cur = list(str(cur))
                    if str_cur[d] == str(m):
                        continue
                    str_cur[d] = str(m)
                    if int(str_cur[d]) < 0:
                        continue
                    next_number = int("".join(str_cur))
                    if next_number >= 1000 and is_prime[next_number] and next_number not in visited:
                        q.append(next_number)
                        visited.add(next_number)
        step += 1
    return "Impossible"

# 에라토스테네스의 체로 먼저 소수체크 배열을 만들어준다.
is_prime = [False, False] + [True] * (10000-2)
for i in range(2, 10000):
    if is_prime[i]:
        for j in range(2*i, 10000, i):
            is_prime[j] = False

t = int(input())
while t:
    a, b = list(map(int, input().split()))
    print(bfs(a, b))
    t -= 1