백준 1963 [소수 경로] 파이썬

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

 

import sys
from collections import deque

# **에라토스테네스의 체를 이용한 소수 판별**
sosu = [True for _ in range(10000)]  # 0부터 9999까지 모든 숫자를 소수(True)로 초기화
sosu[0] = False  # 0은 소수가 아님
sosu[1] = False  # 1도 소수가 아님

# 소수 판별을 위한 에라토스테네스의 체 실행
for i in range(2, 10000):
    if sosu[i]:  # 현재 숫자가 소수라면
        for k in range(i * 2, 10000, i):  # 그 배수들은 모두 소수가 아님
            sosu[k] = False

# **테스트 케이스 개수 입력**
T = int(sys.stdin.readline())

# **각 테스트 케이스 실행**
for _ in range(T):
    success_flg = False  # 목표 수에 도달했는지 확인하는 플래그
    visited = [False for _ in range(10000)]  # 방문 여부를 저장하는 리스트

    # **시작 숫자(start)와 목표 숫자(goal) 입력**
    start, goal = map(int, sys.stdin.readline().split())
    visited[start] = True  # 시작 숫자는 방문 처리

    cnt = 0  # 변경 횟수(최소 변환 횟수)
    q = deque()  # BFS 탐색을 위한 큐
    q.append((start, cnt))  # (현재 숫자, 변경 횟수) 형태로 큐에 추가

    # **BFS 실행**
    while q:
        curr, cnt = q.popleft()  # 현재 숫자와 변경 횟수 가져오기

        # 목표 숫자에 도달한 경우 결과 출력 후 종료
        if curr == goal:
            success_flg = True
            print(cnt)
            break

        cnt += 1  # 숫자를 변경했으므로 변경 횟수 증가

        n_digit_start_num = 100000  # 4자리 숫자에서 각 자릿수를 변경할 때 사용

        # **4자리 숫자의 각 자리 변경**
        for _ in range(4):
            n_digit_start_num //= 10  # 1000 → 100 → 10 → 1 순으로 진행
            temp = n_digit_start_num  # 현재 자리수의 초기값
            temp_n_1 = n_digit_start_num // 10  # 현재 자리보다 작은 자리 (예: 1000일 때 100)

            # 현재 자리의 숫자를 제거한 값 계산
            temp_curr = curr - ((curr // temp_n_1) % 10 * temp_n_1)

            # **0~9까지의 숫자로 해당 자리 변경**
            for _ in range(10):
                temp -= temp_n_1  # 자리값을 감소 (0~9 변환)
                
                # 1000의 자리(첫 번째 자리)가 0이 되면 무시 (네 자리 수 유지)
                if temp == 0 and temp_n_1 == 1000:
                    continue

                new_number = temp_curr + temp  # 변경된 숫자 계산

                # 변경된 숫자가 소수이고, 아직 방문하지 않았다면 큐에 추가
                if sosu[new_number] and not visited[new_number]:
                    visited[new_number] = True  # 방문 처리
                    q.append((new_number, cnt))  # 새로운 숫자를 큐에 추가

    # 목표 숫자에 도달하지 못한 경우 "Impossible" 출력
    if not success_flg:
        print('Impossible')

에라스토테네스의 체와 BFS를 같이 사용하면 된다.