[BOJ1963] 소수 경로

문제

• 4자리 소수를 한 자리씩 바꿔서 목표 소수까지 가는 최소 횟수

입력

• t (testcase)
• t 개의 줄에 1쌍씩 네 자리 소수 (source, destination)

출력

• 각 tc에 두 소수 사이의 변환에 필요한 최소 회수 출력, 불가능인 경우 Impossible

설계

• 에라토스테네스의 체를 이용하여 먼저 소수 구해놓기
• bfs를 이용하여 한 자리씩 바꾸며 체크
• 그래프를 떠올릴 수 있는 것이 관건

How I solved(click to github)

---

ref :
BOJ1963