1963 소수 경로

주어진 소수p를 한 숫자만 바꾸면서 소수 q를 만들려고 한다. 이때 바꾸는 과정에서 나온 숫자도 무조건 소수여야 할 때 최소 몇번을 걸쳐야 되는지를 구하는 문제이다.

이 문제는 다른 소수문제와는 다르게 BFS가 필요한 문제이다. 현재 소수를 큐에 넣은다음, 큐에서 빼내면서 그 소수로 만들 수 있는 다른 소수들을 집어넣어준다.
그런 과정을 계속하면서 카운트를 해주고, q를 발견하면 그 값을 출력하면 된다.
다른 소수를 만드는 방법은 각 자리 숫자들의 숫자를 0~9까지 바꿔가면서 소수판별을 해주면 된다.

소스