반응형 에라토스테네서의 체1 [C/C++] 백준 #1963 소수 경로(너비 우선 탐색) 이번 문제는 소수중 한자리의 숫자만 다른 소수 경로를 찾는 문제입니다. 소수를 찾기 위해서 에라토스테네스의 체를 이용해도 되겠지만, 저는 미리 구한 4자리 소수 집합을 사용했습니다. 약간 편법일 수 있겠지만. 소수의 경로를 찾기 위해서 소수 후보를 찾는 것이 가장 힘듭니다. 일단 4자리 소수는 모두 홀수 소수이므로 갈 수 있는 경로는 31가지가 됩니다. 그것을 생각해서 한자리 숫자들을 바꾸면서 소수면 너비우선탐색 알고리즘으로 방문을 합니다. 그래서 목표하는 소수가 나오면 그때의 경로횟수가 답이 됩니다. 그런데, 모든 갈 수 있는 경로를 다 갔는데, 목표하는 소수가 나오지 않은 경우(queue가 비어있는 경우)에는 불가능하다고 출력을 내면 됩니다. 제가 작성한 소스입니다. //----------------.. 2022. 12. 9. 이전 1 다음 728x90
