BOJ#1963 소수 경로

BOJ#1963 소수 경로

* 문제

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

* 풀이

- 구하는 것 :두 소수 변환에 필요한 최소 변환 횟수

                  (최단 경로, 가중치 1이고 경우의 수가 많지 않으므로 BFS 탐색 가능)

- 조건 : 4자리수, 소수로만 이동 가능, 중복 방문 x

- 예를 들어 Test Case가 '1033 8179'인 경우 

step = 0;

1) 1033에서 한자리수를 변경해서 만들 수 있는 모든 소수들을 구한 후 Queue에 넣는다. (step = 1)

2) step == 1인 Queue에 들어있는 모든 수에 대해 반복 (step = 2)

3) step == 2인 Queue에 들어있는 모든 수에 대해 반복 (step = 3)

....

결국 step == n에서 8179를 찾게 될 것이고, 이 때 step이 우리가 원하는 답이 된다.

더 이상 탐색이 필요하지 않으므로 바로 return 해주면 끝.

* Test Case

13

1231 1231

1231 1237

1277 9001

9001 8087

8263 9391

9011 8263

7433 4133

3797 3467

8017 1373

3391 8017

1109 1019

9173 1973

2441 9199

0

1

5

4

6

6

3

2

7

5

2

2

8

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231963/src/Main.java

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static private int[] d = {1000, 100, 10, 1};
    static private boolean[] isNotPrime = new boolean[10000];
    static private boolean[] discovered = new boolean[10000];

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        findPrimeNum();

        while (T-- > 0) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            if (A == B) {

                bw.write("0\n");
                continue;
            }

            int ret = bfs(A, B);
            bw.write(ret == -1 ? "Impossible\n" : ret + "\n");
        }

        bw.flush();

        bw.close();
        br.close();
    } // main

    static private int bfs(int A, int B) {

        discovered = new boolean[10000];

        Queue<Integer> queue = new LinkedList<>();

        queue.add(A);
        discovered[A] = true;

        int step = -1;

        while (!queue.isEmpty()) {

            step++;

            int size = queue.size();

            for (int i = 0; i < size; i++) {

                int u = queue.poll();

                // 종료 조건
                if (u == B) {

                    return step;
                }

                // u -> 자리수 분할
                int[] cipher = new int[4];
                for (int j = 0; j < 4; j++) {

                    cipher[j] = u / d[j];
                    u %= d[j];
                }

                // 탐색
                for (int j = 0; j < 4; j++) {

                    for (int k = 0; k < 10; k++) {

                        cipher[j] = cipher[j] + 1 > 9 ? 0 : cipher[j] + 1;

                        int nextNum = 0;

                        for (int l = 0; l < 4; l++) {

                            nextNum += cipher[l] * d[l];
                        }

                        // 조건
                        if (nextNum < 1000) continue;
                        if (discovered[nextNum]) continue;
                        if (isNotPrime[nextNum]) continue;

                        queue.add(nextNum);
                        discovered[nextNum] = true;
                    }
                }
            }
        }

        return -1;
    }

    static private void findPrimeNum() {

        for (int i = 2; i < 10000; i++) {

            if (isNotPrime[i]) continue;

            for (int j = 2; i * j < 10000; j++) {

                isNotPrime[i * j] = true;
            }
        }
    }
}