[백준] 1963번 : 소수 경로

1963번: 소수 경로

---

[BFS]

 

4자리 이면서 소수인 숫자를 한 자리씩 바꾸는데, 바꿔서 완성된 4자리 수도 소수이어야 한다. 그래서 목표 소수까지 가야하는데, 한 자리씩 어떻게 바꿀 것 인가에 대한 방법은 다양할 것이다.

 

나는 문자열로 변환하여 풀었다. 예를 들어 1033이라는 수가 있으면, 이를 문자열로 변환하고 1000의 자리, 100의 자리, 10의 자리, 1의 자리에 각각 0~9를 대입하며

(1) 방문했었는지 ?

(2) 4자리 숫자인지 ?

(3) 소수인지 ?

를 따져서 해당 조건을 모두 충족하면 Queue에 넣어 BFS를 수행하였다

 

소수를 판별하는 알고리즘은 숫자 x가 주어졌을 때 2 ~ x의 제곱근까지 나머지 연산을 하며 약수가 있는지 체크하는 것을 사용했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static boolean[] visit;
    static String[] nums = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
    static int[] move;
    
    static boolean isPrime(int x){

        for(int i=2; i<=Math.sqrt(x); i++)
            if(x % i == 0)
                return true;

        return false;
    }

    static void BFS(int s, int e){

        Queue<Integer> Q = new LinkedList<>();
        visit[s] = true;
        move[s] = 0;

        Q.add(s);

        while(!Q.isEmpty()){
            int cur = Q.poll();

            for(int a=0; a<10; a++)
                for(int b=0; b<4; b++){

                    StringBuilder sb = new StringBuilder(Integer.toString(cur));

                    sb.replace(b, b+1, nums[a]);

                    int next = Integer.parseInt(sb.toString());

                    if(next < 1000 || next > 9999 || visit[next] || isPrime(next)) continue;

                    visit[next] = true;
                    move[next] = move[cur] + 1;
                    if(next == e) return;

                    Q.add(next);
                }
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        for(int i=0; i<t; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            visit = new boolean[10000];
            move = new int[10000];
            Arrays.fill(move, -1);

            BFS(a, b);

            System.out.println(move[b] == -1? "impossible" : move[b]);
        }
    }
}

.