[Python] BOJ 1963 - 소수 경로(Prime Path)

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

1963번: 소수 경로

# 카톡방에 누가 질문을 올려서 재밌어보이길래 풀어봤다.

   마침 이번주에 BFS문제를 연속으로 풀고 있어서 쉽게 풀었다.

 

# A를 B로 바꾸는 과정에서도 4자리수가 유지되어야 하고 소수이어야 하므로

   get_primes함수를 통해 1000과 10000사이의 소수를 모두 구해준다. (1060개정도밖에 되지 않는다.)

   get_primes함수에서 소수를 구하는 과정은 '에라토스테네스의 체' 방법을 사용하였다.

 

# bfs함수를 통해 A를 B로 바꾸는데 걸리는 최소 회수를 구해서 return 해준다.

 

* bfs함수: q에서 pop한 숫자가 b이면 B로 바뀐 것이므로 visited[b]를 return해준다.

 

   b가 아니면 이중for문을 통해 각각의 자리수를 0부터 9까지 일일이 다 바꿔보며 new_num에 넣어준다.

   new_num이 1000보다 작거나 q에서 pop한 숫자라면 continue를 해주고

   1000이상이고 소수이고 방문하지 않은 숫자라면 q에 넣어주고 visited에 횟수를 넣어준다.

 

   마지막까지 b에 도달하지 못하면 -1을 return해준다.

 

# 각각의 TestCase 마다 visited를 초기화해주고 bfs함수를 돌려줘서

   res값이 -1이면 impossible을 출력하고 아니면 res를 출력한다.

 

import math, sys
from collections import deque
input = sys.stdin.readline

def get_primes(a, b):
    is_primes = [True] * b
    max_length = math.ceil(math.sqrt(b))
    for i in range(2, max_length):
        if is_primes[i]:
            for j in range(i+i, b, i):
                is_primes[j] = False
    return [i for i in range(a, b) if is_primes[i]]
primes = get_primes(1000, 10000)

def bfs(a, b, visited):
    q.append(a)
    visited[a] = 1
    while q:
        x = str(q.popleft())
        if int(x) == b:
            return visited[b]

        for i in range(4):
            for j in range(10):
                new_num = int(x[:i] + str(j) + x[i+1:])
                if int(x) < 1000 or new_num == int(x):
                    continue
                else:
                    if new_num in primes and not visited[new_num]:
                        q.append(new_num)
                        visited[new_num] = visited[int(x)] + 1
    return -1

T = int(input())
for _ in range(T):
    q = deque()
    a, b = map(int,input().split())
    visited = [0] * 10001
    res = bfs(a, b, visited)
    if res == -1:
        print("impossible")
    else:
        print(res - 1)

(solved.ac 티어: 골드 4)

 

# 나중에 알았는데, impossible인 경우는 없다고 한다.