33. 1963번 소수 경로

 

문제를 쉽게 이해하기위해서 아래 이미지를 가져와보았다.

이러한 형태의 자물쇠를 돌려 소수를 만든다 라고 생각하면 쉽게 이해 할 수 있을 것 같다.

 

우리가 고려해야 할 점은

 

1. 비밀번호는 4자리수이며 현실 비밀번호와달리 문제에서는 0432 와 같은 제일 앞자리가 0이 오는 형태는 가질 수 없다. 즉 1000보다 큰값이라는 말

 

2. 최대 나올수 있는 수는 9999로 에라토스테네스의 체를이용해 미리 10000까지의 소수를 구해놓아야 한다는 것

 

3. 현재암호와 변경된 횟수를 담은 객체가 필요하다는 것

 

4. 해당 객체를 탐색시 탐색된 숫자가 이미 탐색한 숫자이면 처리를 해주어야 한다는 것

 

5. 각 자리수들을 탐색하는데 이전에 탐색했던 숫자이면 넘어가며 동시에 소수이면 횟수를 늘려준다

 

6. 이후에도 탐색했는데도 답이없다면 Impossible

 

위 6가지를 고려하며 코드를 구성해보자

 

 

자물쇠의 현재 숫자와 변경된 횟수를 담고있는 Lock 객체

class Lock {
    int cur;
    // 현재 숫자
    int cnt;
    // 변경된 횟수

    public Lock(int cur, int cnt){
        this.cur = cur;
        this.cnt = cnt;
    }
}

 

입력을 받는 구문

public class Main {

    static int T;
    static boolean[] visited; //방문확인
    static Queue<Lock> queue; //Lock객체타입을 가진 queue
    static int maintain, change;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Testcase = Integer.parseInt(st.nextToken()); //입력받는 케이스의 수

        // maintain = 현재암호 change = 변경암호
        for(int i=0; i<Testcase; i++){
            st = new StringTokenizer(br.readLine());
            maintain = Integer.parseInt(st.nextToken());
            change = Integer.parseInt(st.nextToken());
            queue = new LinkedList<>();
            visited = new boolean[10001];
            
            
            bfs();
        }
    }

 

에라토스테네스의 체 ( 소수를 미리 걸러 놓기 )

public static void PrimeNumber(){
    for(int i=2;i<=9999;i++){
        if(primeNumber[i]==false) {
            for (int j = 2*i; j <= 9999; j += i ) {
                primeNumber[j] = true;
            }
        }
    }
}

 

bfs 탐색

private static void bfs(){
        queue.add(new Lock(start,0));

        // 암호가 변경되지 않았을 경우, 0 출력
        if(maintain == change){
            System.out.println(0);
            return;
        }

        while(!queue.isEmpty()){
            Lock lock = queue.poll();
            //현재 방문한 위치가 기존에 방문 하지않았더라면
            if(!visited[Lock.cur]){
                visited[Lock.cur] = true; 

                //암호들을 바꾸는 반복 시작
                for(int i=0; i<=9; i++){
                    for(int j=0; j<4; j++){
                        // 천의 자리숫자는 0이면 안되니까 패스
                        if(i==0 && j==0){
                            continue;
                        }

                        // 조각낸 걸 문자형으로 배열에 담아준다
                        char[] each_numbers = Integer.toString(Lock.cur).toCharArray();    
												
                        // 초기화를 위한 설정
                        char origin = each_numbers[j];

                        // 문자형을 int형으로 -> 0에 해당하는 48을 더해주고 시작
                        each_numbers[j] = (char)(i+48);

                        // 소수 판별을 위해 Int 형으로 바꿔놓음
                        int n = Integer.parseInt(String.valueOf(each_numbers));

                        // 다시 char 형으로 초기화
                        each_numbers[j] = origin;

                        if(visited[n]){ //변경된 암호가 이미 탐색했던곳이라면
                            continue;
                        }
                        if(PrimeNumber(n)){ //아니면 소수 판별
                            if(n == end){ //소수이고 바뀐 암호가 최종암호면
                                System.out.println(Pw.cnt + 1); //카운팅
                                return;
                            }
                            queue.add(new pw(n, Pw.cnt + 1)); //아니면 카운팅+큐에 추가
                        }

                    }
                }
            }
        }
        System.out.println("Impossible");
    }