[java 백준]골드 4/ 1963번 소수경로

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

1963번: 소수 경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int n, first, last;
 
    public static boolean[] prime = new boolean[10000];
 
    public static int div[] = { 1000, 100, 10, 1 };
 
    public static int BFS(int n) {
        int cnt = -1;
 
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] visited = new boolean[10000];// visited도 초기화
 
        queue.add(n);
        visited[n] = true;
        while (!queue.isEmpty()) {
 
            cnt++;
 
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                if (node == last) {
 
                    return cnt;
                }
                int[] arr = new int[4];
                for (int j = 0; j < 4; j++) {
                    arr[j] = node / div[j];
                    node %= div[j];
                }
 
                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 10; k++) {
                        if (arr[j] + 1 > 9) {
                            arr[j] = 0;
                        } else {
                            arr[j]++;
                        }
                        int num = 0;
                        for (int l = 0; l < 4; l++) {
                            num += arr[l] * div[l];
                        }
 
                        if (num >= 1000 && !visited[num] && !prime[num]) {
 
                            queue.add(num);
                            visited[num] = true;
                        }
                    }
 
                }
 
            }
 
        }
 
        return -1;
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        Scanner sc = new Scanner(System.in);
        n = Integer.parseInt(br.readLine());
 
        prime[0] = prime[1] = true;
 
        for (int i = 2; i < 10000; i++) {
            if (!prime[i]) {// 만약 prime[i]가 소수라면
                for (int j = 2; j * i < 10000; j++) {
                    prime[j * i] = true;
                }
            }
        }
 
        for (int k = 0; k < n; k++) {
            st = new StringTokenizer(br.readLine());
            first = Integer.parseInt(st.nextToken());
            last = Integer.parseInt(st.nextToken());
 
            int ans = BFS(first);
            if (ans != -1) {
                System.out.println(ans);
 
            } else {
                System.out.println("Impossible");
            }
 
        }
 
    }
 
}

 

우선 소수판별을 에라토스테네스의 체를 사용하고 -> BFS탐색해주면서 첫번째 자리만 바꿨을때/두번째 자리만 바꿨을 때/세번째 자리만 바꿨을 때/네번째 자리만 바꿨을 때 소수일 경우 큐에 넣어준다 는 것 까진 생각해냈는데 어찌된건지 중간에 스텝이 꼬여서 춤추는 개발자님의 코드를 참고했다.

아래는 내가 스텝이 꼬인이유를 적어봤다.

 

1.자리수 분할할때 string이 아닌 int형으로만 분할해주기 (시간초과 예방)

만약에 1033이 들어오면 arr[0]은 1이 들어가고 나머지 애들인 33은 1033%1000의 결과이기에 node가 33으로 바뀌는 식이다.

나는 string배열로 바꿔서 문제를 풀었는데 이러니까 코드가 너무 길어지고 시간초과에 걸릴 위험이 컸다. 

 

 

2. 어떤게 queue에 들어와도 결국 최종 cnt(개수)는 같다!

 

1033을 한번 탐색하고 나면 큐에는 1433,1733,1933 등등의 숫자가 들어온다. 나는 발문에서 1033이후에 바로 1733이 나와서 1733이 아니면 답이 달리지는 줄 알았다. 근데 1433,1733,1933 등 그 회차에 첫번째 자리부터 네번째자리 까지 하나씩만 바꿨을 때 소수로 판별된 애들을 BFS돌려주면 결국 최종 cnt는 다 똑같았다! 

 

3.(중요!) visited는 BFS메서드가 새로 시작할때마다 초기화 해줘야 한다!

 

너무 당연하지만 항상 이런데서 놓친다..ㅋㅋ

 

참고 사이트 

https://log-laboratory.tistory.com/113

[백준] 1963번 자바 소수 경로