소수 경로

• 기본적으로는 BFS로 최단 경로를 구하는 문제이다.
• 각 숫자에서 한자리만 바꿔서 만들수 있는 숫자 9*4=36개중에서 소수인 것들을 찾아서 큐에 넣어주면 된다. 매번 어떤 수가 소수인지 확인을 해야 하기 때문에, 미리 1000부터 9999까지의 소수 목록을 계산해놓을 필요가 있다.
• T가 크다면 모든 소수에 대해서 바꿀수 있는 소수들을 미리 모두 계산해서 그래프를 완성시켜놓고서, 각 테스트 케이스들에 대해서 그 그래프를 사용하는 것이, 매번 엣지들을 다시 계산하지 않아도 되니까 효율적일수 있다. T가 작은 편이라면 그래프를 전부 다 만들어 놓는 것은 방문하지 않을 노드들에도 불필요하게 엣지를 계산하게 되니까 비효율적일수 있다. 문제는 T값의 범위가 주어지지 않는다는 점.. 그냥 그래프를 완성시켜놓고 푸는 방식으로 구현했다.
• n이하의 소수 목록을 구하는 것은 O(nloglogn). 여기에서 n=10000이다. 한번 BFS를 도는데 시간복잡도는 O(V+E) 이다. V의 값은 대충 1000 정도이고 (1000~9999 사이의 소수의 갯수), E의 값은 대충 1000 * 36*0.12 정도이다. (0.12 = 10000이하의 임의의 수가 소수일 확률..). 그냥 상수취급 해버린다면 O(1)이 되기는 한다.
• 재미있게도, 'Impossible'을 출력해야 하는 경우는 생기지 않는다. 다시 말하면, 모든 4자리 소수들 사이에는 소수 경로가 존재한다.

"""Solution code for "BOJ 1963. 소수 경로".

- Problem link: https://www.acmicpc.net/problem/1963
- Solution link: http://www.teferi.net/ps/problems/boj/1963

Tags: [Prime Number], [BFS]
"""

import itertools
from teflib import numtheory
from teflib import tgraph

INF = float('inf')


def main():
    primes = set(numtheory.prime_list(1000, 9999))
    graph = [[] for _ in range(10000)]
    for num in primes:
        for nk, k in itertools.pairwise([10000, 1000, 100, 10, 1]):
            beg = num // nk * nk + num % k
            graph[num].extend(x for x in range(beg, beg + nk, k) if x in primes)

    T = int(input())
    for _ in range(T):
        source, dest = [int(x) for x in input().split()]
        answer = tgraph.min_distance_to_dest(graph, source, dest)
        print('Impossible' if answer == INF else answer)


if __name__ == '__main__':
    main()

• Dependency:
  • teflib.numtheory.prime_list
  • teflib.tgraph.min_distance_to_dest