[Baekjoon] 1963번: 소수 경로

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

1963번: 소수 경로

문제 설명

소수 A를 소수 B로 바꾸는 최소 단계를 구해야 한다. A를 B로 바꿀 때는 한 자릿수만 바꿀 수 있으며 바꾼 수 또한 소수여야 한다. 또한 네 자리 소수만 허용하므로 0039와 같은 수는 안 된다.

풀이 방법

이 문제는 소수 구하기와 BFS가 결합된 문제이다.

소수 구하기

에라토스테네스의 체를 활용해서 해결한다.

import java.io.*;
import java.util.*;

class Main {

    private static final int MAX = 9999;
    private static boolean[] sieve = new boolean[MAX + 1];
    
    public static void main(String[] args) throws IOException {
        init();
        // ...
    }
    
    private static void init() {
        for (int i = 2; i <= Math.sqrt(MAX); i++) {
            if (sieve[i] == true) continue;
            
            for (int j = i + i; j <= MAX; j += i) {
                sieve[j] = true;
            }
        }
    }
}

BFS

이 문제를 해결하려면 소수 A에서 한 자릿수를 바꾼 모든 소수를 탐색해 나가야 한다. 따라서 천의 자리부터 일의 자리까지 모두 한 자리씩 바꾼 후 그 바꾼 소수에서 또 다시 소수 B를 찾기 위해 천의 자리부터 일의 자리까지 바꿔가면서 구해야 한다. 따라서 BFS를 활용하는 편이 효율적이라고 판단할 수 있다.

또 다른 문제는 숫자를 한 자리씩 바꾸어 가는 것이다. 문자열로 처리할 수 있지만 int로 처리할 때보다 성능이 떨어지므로 int형으로 해결한다.

import java.io.*;
import java.util.*;

class Main {

    private static final int MAX = 9999;
    private static int[] cnt;
    private static int[] d = {1000, 100, 10, 1};
    private static boolean[] isVisited;
    private static boolean[] sieve = new boolean[MAX + 1];
    
    public static void main(String[] args) throws IOException {
        // ...
        
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            String[] split = br.readLine().split(" ");
            int src = Integer.parseInt(split[0]);
            int dst = Integer.parseInt(split[1]);
            cnt = new int[MAX + 1];
            isVisited = new boolean[MAX + 1];
            
            translate(src, dst);
            
            if (!isVisited[dst]) {
                sb.append("Impossible").append("\n");
            } else {
                sb.append(cnt[dst]).append("\n");
            }
        }
        
        System.out.print(sb);
    }
    
    private static void translate(int src, int dst) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(src);
        isVisited[src] = true;

        while (!q.isEmpty()) {
            int curPrime = q.poll();

            if (curPrime == dst) {
                return;
            }

            for (int i = 0; i < 4; i++) {
                int val = curPrime / d[i] / 10; // 바꿀 자릿수의 왼쪽 부분
                int mod = curPrime % d[i];      // 바꿀 자릿수의 오른쪽 부분

                for (int j = 0; j <= 9; j++) {
                    if (i == 0 && j == 0) // 천의 자리가 0이면 안 된다
                        continue;

                    // 자릿수를 바꾼 수
                    int next = (val * d[i] * 10) + (j * d[i]) + mod;
                    // 방문한 적 없고 소수라면 큐에 추가하고 카운트 증가
                    if (!isVisited[next] && !sieve[next]) {
                        q.offer(next);
                        isVisited[next] = true;
                        cnt[next] = cnt[curPrime] + 1;
                    }
                }
            }
        }
    }
    
    // ...
}