백준 1963 소수 경로 (Java)

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Pair{
    Integer data;
    int cnt;

    public Pair(int data, int cnt) {
        this.data = data;
        this.cnt = cnt;
    }

}

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

        int t;


        boolean[] notPrime = new boolean[10000];
        notPrime[0] = notPrime[1] = true;
        for (int i = 2; i < 10000; i++) {
            if (!notPrime[i]) {
                for (int j = i + i; j < 10000; j += i) {
                    notPrime[j] = true;
                }
            }
        }


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        t = Integer.parseInt(br.readLine());

        for (int test = 0; test < t; test++) {

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

            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            int ans = 987654321;
            boolean possible = false;
            boolean[] visit = new boolean[10000];

            Queue<Pair> qu = new ArrayDeque<>();

            qu.offer(new Pair(a, 0));
            visit[a] = true;

            while (!qu.isEmpty()) {

                Pair cur = qu.poll();

                if (cur.data == b) {
                    ans = Math.min(ans, cur.cnt);
                }


                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 10; j++) {
                        if (i == 0 && j == 0) {
                            continue;
                        }

                        StringBuilder sb = new StringBuilder(String.valueOf(cur.data));
                        sb.setCharAt(i, (char) (j + '0'));
                        int next = Integer.parseInt(sb.toString());

                        if (!notPrime[next] && !visit[next]) {
                            visit[next] = true;
                            qu.offer(new Pair(next, cur.cnt + 1));
                        }

                    }
                }

            }

            if (ans == 987654321) {
                System.out.println("Impossible");
            } else {
                System.out.println(ans);
            }

        }

    }
}

1. 문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

2. 풀이

a에서 특정 경로를 통해 b로 가는 문제이다. 각 경로에는 현재 숫자에서 한 자리를 다른 숫자로 바꾸어 네 자리 소수를 만드는 경우만 가능하다. 이를 토대로 문제를 풀어보자.

        boolean[] notPrime = new boolean[10000];
        notPrime[0] = notPrime[1] = true;
        for (int i = 2; i < 10000; i++) {
            if (!notPrime[i]) {
                for (int j = i + i; j < 10000; j += i) {
                    notPrime[j] = true;
                }
            }
        }

우선 에라토스테네스의 체를 이용하여 10000 보다 작은 모든 소수를 구한다. 

class Pair{
    Integer data;
    int cnt;

    public Pair(int data, int cnt) {
        this.data = data;
        this.cnt = cnt;
    }

}




....

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

            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            int ans = 987654321;
            boolean[] visit = new boolean[10000];

            Queue<Pair> qu = new ArrayDeque<>();

            qu.offer(new Pair(a, 0));
            visit[a] = true;

 각 테스트에 대해 입력을 받고, 해당 숫자를 만든 적이 있는지에 대한 boolean 배열을 선언한다. 해당 숫자와 이를 만들기 위한 연산 횟수를 기록하기 위해 Pair 클래스를 만들고, 큐에 초기값을 넣는다.

 while (!qu.isEmpty()) {

                Pair cur = qu.poll();

                if (cur.data == b) {
                    ans = Math.min(ans, cur.cnt);
                }


                for (int i = 0; i < 4; i++) {
                    for (int j = 0; j < 10; j++) {
                        if (i == 0 && j == 0) {
                            continue;
                        }

                        StringBuilder sb = new StringBuilder(String.valueOf(cur.data));
                        sb.setCharAt(i, (char) (j + '0'));
                        int next = Integer.parseInt(sb.toString());

                        if (!notPrime[next] && !visit[next]) {
                            visit[next] = true;
                            qu.offer(new Pair(next, cur.cnt + 1));
                        }

                    }
                }

            }

            if (ans == 987654321) {
                System.out.println("Impossible");
            } else {
                System.out.println(ans);
            }

 이제 BFS를 돌린다. 각 연산마다 모든 자릿수에 대해 숫자를 바꾼다. 단, 네 자리 소수이므로 앞 자리를 0으로 바꾸거나, 바꾸었는데 소수가 아니면 안된다. 해당 숫자를 방문하지 않은 것까지 확인했다면, {다음 숫자, 현재 연산+1}을 큐에 넣는다. 돌다가 목표 숫자인 b를 찾았다면 정답을 갱신한다.

 모두 돌았음에도 숫자를 찾지 못했다면 Impossible을, 찾았다면 해당 연산 횟수를 출력해주면 된다.