[BOJ 1963] 소수 경로

문제 링크 : https://www.acmicpc.net/problem/1963

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

제한

시간 제한	메모리 제한
2sec	256MB

---

풀이

이 문제는 4자리 소수 $A$를 한 번에 한 자리씩만 바꾸어 소수 $B$로 만드는 최소 변환 횟수를 구하는 문제이다. 각 단계에서 생성되는 숫자 또한 반드시 4자리 소수여야 한다는 제약 조건이 있으며, 최단 경로를 찾아야 하므로 너비 우선 탐색(BFS) 알고리즘을 사용한다.

구현 로직은 다음과 같다:

• 소수 사전 판별: 에라토스테네스의 체를 사용하여 $10\,000$ 미만의 모든 수에 대해 소수 여부를 미리 판별한다. 이를 통해 BFS 탐색 중 매번 소수 판별 연산을 수행하는 비용을 줄일 수 있다.
• BFS 탐색: 시작 소수 $A$부터 탐색을 시작하며, 큐에는 현재 숫자와 지금까지의 변환 횟수를 저장한다.
• 인접 정점 생성: 현재 숫자의 각 자릿수(천의 자리, 백의 자리, 십의 자리, 일의 자리)를 $0$부터 $9$까지 변경하여 다음 후보 숫자를 생성한다.
  • 새로 만든 숫자가 $1\,000$ 이상이고 소수이며 아직 방문하지 않은 경우에만 큐에 추가하고 방문 표시를 한다.
• 목표 도달: 탐색 중 목표 소수 $B$를 발견하면 현재까지의 변환 횟수를 출력한다. 만약 큐가 빌 때까지 $B$를 찾지 못한다면 “Impossible”을 출력한다.

탐색 범위가 $1\,000$에서 $9\,999$ 사이의 소수들로 제한되어 있어 상태 공간이 매우 작으므로, BFS를 통해 효율적으로 정답을 도출할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 너비 우선 탐색(BFS), 에라토스테네스의 체