[백준-1963]-[BFS]-소수경로

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

---

이 문제는 까먹었던 소수에대해서 다시 기억하게 해준 고마운 문제다. 

먼저 소수는 1 과 자신 이외에 나누어지지 않는 수를 소수라고 한다. 

그럼 소수인지 아닌지 어떻게 확인할까??

N이라는 수가 있다면 2부터 N 전의 정수로 전부 나눠서 하나라도 나누어지는 값이 있다면 그것은 소수가 아니고 나누어지는 값이 없다면 그 값은 소수이다. 

1은 소수가 아니다. 

그래서 1은 예외처리를 해줘야 한다. 

소수 판별하는 소스

    public static boolean isPrimeNum (int num) {
        boolean result = true;
        
        if(num == 1) return false;
        
        for(int i = 2; i < num; i++) {
            if(num%i == 0) {
                result = false;
                break;
            }
        }
        return result;
    }

이문제를 어떻게 접근할까 하다가 주어지는 수는 1000에서 9999까지의 네자리 수 실수가 주어진다고 한다. 

그럼 1000 부터 9999까지 실수를 먼저 구해놓으면 나중에 시간이 덜 들 수 있어 보인다. 

그리고 입력 받은 시작 값에서 목표 값까지 가기위해 BFS로 실수 인것들의 수를 세어 보았다. 

BFS 소스 

    public static void bfs(int startNum, int endNum) {
        int count = -1;
        boolean[] visited = new boolean[10000];
 
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{startNum, 0});
        
        while(!queue.isEmpty()) {
            int num = queue.peek()[0];
            int cnt = queue.peek()[1];
            queue.poll();
            if(num == endNum) {
                if(count == -1 || count > cnt) count = cnt;
                continue;
            }
            if(num < 1000 || visited[num]) continue;
            
            visited[num] = true;
            
            for(int i=1; i <= 4; i++) {
                for(int j = 0; j < 10; j++) {
                    int tNum = changeNum(num, i, j);
                    if(tNum >= 1000 && prime[tNum]) {
                        queue.offer(new int[] {tNum, cnt+1});
                    }
                }
            }
        }
        
        if(count == -1) System.out.println("Impossible");
        else System.out.println(count);
    }

나머지는 전형적인 BFS 이고 20 번째 줄이 이번 문제에 특징을 가지고 있는 부분이다. 

이중포문으로 구성되어 있는데 바깥 for문은 1000 자리부터 1의 자리까지 의 타입을 1~4로 나타낸것이다.

안쪽 for문은 특정 자리수의 0 ~ 9 까지 반복하면서 수를 변경하기위해 사용했다. 

변경한 수가 소수이면 큐에 저장하고 계속 반복하면 된다. 

나머지는 전체 소스를 보면서 이해하면 될거 같다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static boolean[] prime;
    
    public static int[][] primeArr;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int size = Integer.parseInt(br.readLine());
 
        prime= new boolean[10000];
        primeArr = new int[size][10000];
        
        for(int i = 1000; i < 10000; i++) {
            prime[i] = isPrimeNum(i);
        }
        
        for(int i = 0; i < size; i++) {
            st = new StringTokenizer(br.readLine());
            int startNum = Integer.parseInt(st.nextToken());
            int endNum = Integer.parseInt(st.nextToken());
            bfs(startNum, endNum);
        }
    }
    public static void bfs(int startNum, int endNum) {
        int count = -1;
        boolean[] visited = new boolean[10000];
 
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{startNum, 0});
        
        while(!queue.isEmpty()) {
            int num = queue.peek()[0];
            int cnt = queue.peek()[1];
            queue.poll();
            if(num == endNum) {
                if(count == -1 || count > cnt) count = cnt;
                continue;
            }
            if(num < 1000 || visited[num]) continue;
            
            visited[num] = true;
            
            for(int i=1; i <= 4; i++) {
                for(int j = 0; j < 10; j++) {
                    int tNum = changeNum(num, i, j);
                    if(tNum >= 1000 && prime[tNum]) {
                        queue.offer(new int[] {tNum, cnt+1});
                    }
                }
            }
        }
        
        if(count == -1) System.out.println("Impossible");
        else System.out.println(count);
    }
    
    public static int changeNum(int num, int type, int t) {
        int resultNum = 0;
        switch(type) {
        case 1:    // 1000 의 자리
            resultNum = t * 1000;
            resultNum += (num - num/1000*1000);
            break;
        case 2:    // 100 의 자리
            resultNum = t * 100;
            resultNum += (num / 1000 * 1000) + (num - num / 100 * 100);
            break;
        case 3:    // 10의 자리
            resultNum = t * 10;
            resultNum += num/100*100 + (num - num / 10*10);
            break;
        case 4:    // 1 의 자리
            resultNum = t;
            resultNum += num / 10 * 10;
            break;
        }
        return resultNum;
    }
    public static boolean isPrimeNum (int num) {
        boolean result = true;
        
        if(num == 1) return false;
        
        for(int i = 2; i < num; i++) {
            if(num%i == 0) {
                result = false;
                break;
            }
        }
        return result;
    }
}