[BOJ] 1963번 소수 경로 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

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 {
    static class Number {
        int num;
        int cnt;

        public Number(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }

    static int T, source, target, min;
    static boolean[] prime, used;
    static final int MAX_VAL = 10000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            init(br);
            process(sb);
        }
        print(sb);
    }

    private static void init(BufferedReader br) throws IOException {
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        source = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
        min = Integer.MAX_VALUE;
        prime = new boolean[MAX_VAL + 1];
        used = new boolean[MAX_VAL + 1];
    }

    private static void process(StringBuilder sb) {
        primeNumberChecked(prime);
        bfs(source);
        setResult(sb);
    }

    static void primeNumberChecked(boolean[] b) {
        b[0] = true; // 소수면 false, 소수가 아니면 true
        b[1] = true;

        for (int i = 2; i < Math.sqrt(MAX_VAL); i++) {
            if (!b[i]) {
                // 2를 예를 들면 2를 제외한 2의 배수는 2로 나뉘어지니 소수가 아님
                for (int j = i * i; j <= MAX_VAL; j += i) {
                    b[j] = true;
                }
            }
        }
    }

    private static void bfs(int start) {
        Queue<Number> q = new LinkedList<>();
        used[start] = true;
        q.add(new Number(start, 0));
        while (!q.isEmpty()) {
            Number now = q.poll();
            int nowNum = now.num;
            int cnt = now.cnt;
            if (nowNum == target) {
                min = Math.min(min, cnt);
            }
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 10; j++) {
                    if (i == 0 && j == 0) continue;
                    int nextNum = change(now.num, i, j);
                    if (prime[nextNum] || used[nextNum]) continue;
                    used[nextNum] = true;
                    q.add(new Number(nextNum, cnt + 1));
                }
            }
        }
    }

    private static void setResult(StringBuilder sb) {
        if (min != Integer.MAX_VALUE) sb.append(min).append("\n");
        else sb.append("impossible\n");
    }

    private static int change(int num, int i, int j) {
        StringBuilder sb = new StringBuilder(String.valueOf(num));
        sb.setCharAt(i, (char) (j + '0'));
        return Integer.parseInt(sb.toString());
    }

    private static void print(StringBuilder sb) {
        System.out.println(sb);
    }
}

📄 해설

• 에라토스테네스의 체 알고리즘을 사용해 소수를 판별하고, BFS 탐색을 수행해야하는 문제
• 에라토스테네스의 체 알고리즘에 대한 작성자의 글은 아래 링크
  작성자의 글(작성 중)
• source 를 target 로 바꾸는데 필요한 최소 횟수를 구하는 문제

접근(동작 흐름)

1. 먼저 10,000 까지의 모든 소수를 구함 (boolean 배열을 이용한 에라토스테네스의 체 구현)
2. 소수가 구해졌으므로, BFS 를 수행하여 source 를 구성하는 숫자를 하나씩 바꿔가며 target 이 되는지를 확인
3. target 이 되면 최솟값을 갱신
4. 최솟값을 출력한다. 이때, 최솟값이 갱신되지 않았으면 impossible 을 출력

이제 상세 흐름을 살펴보자
1번의 경우는 에라토스테네스의 체 알고리즘을 공부하고오면 바로 끝이다 => 생략
2번의 경우, source 를 큐의 시작 노드로 설정하고, 반복을 수행

• 큐에서 꺼낼 때 해당 수가 target 인지를 확인
• 아래의 반복문으로 넘어가면 i 는 0 부터 4까지, j 는 0 부터 9 까지 수행하는데, 이 의미는
  • i 는 자릿수를 의미(첫번째 ~ 네번째 자리를 바꿀 것인지를 선택)
  • j 는 바뀔 수를 의미(0~9까지 각 자리의 수로 바꿔봄)
  • 이때, 4자리 수여야하므로 i == 0 && j == 0 일 경우 넘어간다.
  • 그 다음 change 메소드를 통하여 i 에 해당하는 수를 j 로 바꾸고, 그 수가 소수이고, 확인하지 않은 수라면 큐에 넣고 방문 처리를 함
• 결과적으로 2~3번을 반복하면 되는 문제
• 작성자의 경우 change 메소드 부분을 수학 연산으로 하려다가 코드가 엄청나게 꼬여버렸음(수학도 못하는데) 항상 단순하고 쉬운 접근부터 하는 것을 잊지 말자