[백준/알고리즘] 1963번 소수경로 (골드 5)
BOJ 1963번 소수 A, B가 주어진다. 소수 A에서, 각 자릿수 중 하나를 변경해서 다른 소수로 바꿀 수 있다. 소수 A에서 B로 바꿀 때, 변환에 필요한 최소 횟수를 출력하시오. 불가능한 경우 Impossible을 출력한다. 풀이 알고리즘 : BFS, 탐색 먼저 네자릿수 정수가 소수임을 계속 확인해야 하므로, 에라토스테네스의 체를 이용하여, isPrime 배열에 소수인지 아닌지를 저장해 둔다. 이후 시작하는 정수 a를 큐에 입력하고, BFS를 시작한다. BFS에서 다음 소수로 넘어가기 위한 조건은, 각 자릿수(0, 1, 2, 3번째 각각)를 0부터 9까지 하나씩 넣어보면서, 1. 첫번째 숫자를 0으로 바꾸는 경우 - 불가능 2. 해당 숫자가 소수이고, 이전에 탐색하지 않은 경우 - 가능 두 가지 ..
