[백준] 1963번: 소수경로

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

풀이

BFS+소수 구하기 문제이다.

1.

네 자리수에 대하여 각 자리수의 숫자를 바꿔가면서 모두 탐색해보면 된다.

탐색조건은 1. 아직 방문하지 않은 숫자 2. 소수 3. 1000~9999인 숫자 이다.

 

2.

테스트 케이스 입력받기 전에, 일단 나는 소수를 미리 구해놓았다.

소수를 구하는 방법 중에 '에라토스테네스의 체'를 이용하여 1차원 bool형의 배열에 1부터 9999까지 소수면 false, 소수가 아니면 true를 저장해놓았다.

'에라토스테네스의 체'의 시간복잡도는 O(Nlog(logN))이다. 배열에 먼저 소수인지 아닌지 체크만 해놓으면 나중에 BFS하면서 방문할때 해당 수가 소수인지 아닌지 바로 배열로 참조가능하므로 상수시간으로 체크할 수 있다.

 

[출처] 위키백과: 에라토스테네스의 체

3.

소수 테이블을 미리 다 만들었으면,

이제 입력받은 첫번째 수부터 BFS탐색을 시작한다.

나는 천의자리수를 바꿨을 때, 백의자리수를 바꿨을 때, 십의자리수를 바꿨을 때, 일의자리수를 바꿨을 때 이렇게 네가지 경우를 두었다.

천의자리수 같은 경우에는 가능한 숫자가 1에서 9까지 가능하다. 나머지는 0~9가 가능하다. (왜냐하면 숫자는 무조건 네자리수이어야 하기 때문)

 

4.

천의자리수 for(i: 1~9)로 바꾸고, 바뀐 그 수를 이미 방문한 적이 있는지, 소수인지 판별한 후 큐에 넣을지 말지를 결정했다. 백, 십, 일도 마찬가지!

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1963.cpp

결과