테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 소수 경로 ======

===== 풀이 =====
  * 기본적으로는 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자리 소수들 사이에는 소수 경로가 존재한다.

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: 
    * [[:ps:teflib:numtheory#prime_list|teflib.numtheory.prime_list]]
    * [[:ps:teflib:tgraph#min_distance_to_dest|teflib.tgraph.min_distance_to_dest]]

{{tag>BOJ ps:problems:boj:골드_4}}