[백준] 1963 소수 경로

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

에라토스테네스의 체를 이용하여 소수를 구하였고, 여러 테스트 케이스마다 소수를 구하지 않도록 전역에서 필요한 소수들을 모두 구한 후 테스트케이스의 정답을 찾아나갔습니다.

 

각 자릿수 변경을 BFS 탐색을 이용하였는데, 반복문을 이용하여 각 자릿수를 변경해서 탐색을 진행하였습니다.

2) 알고리즘

• 에라토스테네스의 체
• BFS

3) 풀이 코드

사용 언어 - Python

import sys
import math
from collections import deque
sys.stdin = open('input.txt')


def solution(n):
    q = deque([n])
    visited[n] = 0                      # 시작 숫자는 0번 바꿔서 돌아오므로 0으로 지정
    
    while q:
        if visited[target] < 1e10:      # 목표 숫자로 변환이 가능한 경우, 종료
            return

        node = q.popleft()
        for i in range(4):                                      # 숫자가 4자리 이므로 10의 0, 1, 2, 3 제곱을 하기 위해 4번 반복
            sign = False                                        # 자릿수 올림이 되는지 여부 변수

            for j in range(1, 10):                              # 현재 자릿수를 1부터 9까지 더하면서 바꿈
                next_number = node + 10**i*j                    # 다음 숫자는 현재 숫자의 10의 i 제곱 * j
                
                if not sign and str(next_number)[-i-1] == '0':  # 현재 변경중인 자릿수가 0이라면 올림이 발생하므로
                    sign = True                                 # 올림 여부 변수 True로 변경
                
                if sign:                                        # 올림이 발생했다면
                    next_number -= 10**(i+1)                    # 앞자리 올림 빼기

                if prime_number[next_number] and 1000 <= next_number < 10000 and visited[next_number] == 1e10:      # 소수이고, 4자리 숫자이고, 아직 확인하지 않은 숫자인 경우
                    visited[next_number] = visited[node] + 1    # 몇번 변환이 필요한지 저장
                    q.append(next_number)                       # 다음 탐색


T = int(sys.stdin.readline())                       # 테스트 케이스 개수
prime_number = [True] * 10000                       # 0 ~ 10000 숫자들의 소수 여부 판별 저장 리스트
prime_number[0], prime_number[1] = False, False     # 0과 1은 소수가 아니다

for i in range(2, int(10000**0.5)+1):               # 숫자 2부터 10000의 제곱근의 수까지 반복하여 확인
    for j in range(2, 10000//i+1):                  
        if i*j == 10000: break                      # 인덱스 에러 방지 ex) i = 2 일때, j는 5000까지 나오게 되서 인덱스가 10000 이 되는 경우를 막아야함
        prime_number[i*j] = False                   # 현재 숫자의 배수들은 모두 소수가 아니다

for _ in range(T):
    start, target = map(int, sys.stdin.readline().split())      # 시작 소수, 도착 소수
    visited = [1e10] * 10000                                    # 각 숫자로 변환을 했는지 여부

    solution(start)                 # 탐색

    if visited[target] < 1e10:      # 출력
        print(visited[target])
    else:
        print('Impossible')

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

시간을 절약하기 위하여 매번 모든 수를 탐색하는것이 아닌, 반복문으로 자릿수 변경과 올림을 처리하는 과정에서 인덱스 관리에 다소 어려움을 겪었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

1963번: 소수 경로

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다