[백준] 1963번 : 소수 경로 Gold4(골드4) - JAVA[자바]

[Gold IV] 소수 경로 - 1963

문제 링크

성능 요약

메모리: 17916 KB, 시간: 200 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2023년 11월 28일 10:41:32

문제 설명

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

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

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

입력

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

출력

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

 

 

풀이 방식

1. 한번에 한자리를 바꿀 수 있다.

2. 맨 앞자리부터 한자리씩 바꿔보기

3. 1000미만이거나 소수가 아니면 호출하지 않음 방문 후 -> 그 값으로 또 갈 수 있음 (Map으로 처리)

4. N == end값이라면 result = count 값 넣은 뒤 return

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int result;
    static boolean[] prime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        // 에라토스테네스의 체 알고리즘으로 소수 미리 구하기
        getPrime();
        StringTokenizer st;
        for(int i = 1; i <= t;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            result = -1;
            solution(start,end);
            sb.append(result == -1?"Impossible":result).append("\n");
        }
        System.out.println(sb.toString());
    }
    private static void solution(int start, int end) {
        // 값을 확인하기 위해서 큐를 생성
        Queue<Integer> q = new LinkedList<>();
        // 카운트 값을 저장하기 위한 map
        Map<Integer, Integer> map = new HashMap<>();

        map.put(start, 0);
        q.add(start);
        while(!q.isEmpty()){
            int pos = q.poll();
            int count = map.get(pos);

            if(pos == end){
                result = count;
                return;
            }

            // 첫번째 자리 수, 두번째 자리 수, 세번째 자리 수, 네번째 자리 수를 구해놓음
            int[] pNum = {pos / 1000, (pos / 100) % 10, (pos / 10) % 10, pos % 10};
            for(int i = 0; i < 4; i++){
                for(int j = 0 ; j < 10; j++){
                    // 1000미만은 처리 x
                    if(i == 0 && j == 0) continue;

                    // 해당 자릿값 임시 저장
                    int tmp = pNum[i];
                    pNum[i] = j;
                    // 값 삽입 후 정수로 변환
                    int next = 0;
                    for(int k = 0; k <4; k++){
                        next += (int) (pNum[k] * (Math.pow(10, 3 - k)));
                    }
                    // 다시 원래 숫자로 복구
                    pNum[i] = tmp;

                    // 이미 방문했거나 소수가 아니라면 continue;
                    if(prime[next] || map.containsKey(next)) continue;

                    q.add(next);
                    map.put(next,count+1);
                }
            }
        }
    }

    private static void getPrime(){
        prime = new boolean[10000];
        prime[1] = true;
        for(int i = 2; i <= (int)Math.sqrt(prime.length); i++){
            if(prime[i]) continue;

            for(int j =  i + i; j < prime.length; j+= i){
                prime[j] = true;
            }
        }
    }
}