Competition/Baekjoon

[백준] 1963번 자바 소수 경로

bisi 2020. 4. 21. 11:38
문제 출처 

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

 

1963번: 소수 경로

문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아.

www.acmicpc.net

 

 

 

접근 방식 및 풀이

- 소수 구하기와 BFS 응용 문제

- 비밀번호의 수의 범위가 4자리 수 즉, 1000~9999사이의 소수를 판별하는 것이기 때문에, 에라토스테네스의 체 알고리즘으로 사전에 구해 놓는다. 

- 배열별로 담겨 있던 숫자들을 소수와 비교하여 비밀번호가 일치하면 step 카운트 출력

- 나머지 내용은 코드 주석을 참고해주세요.

- 블로그 참고 

 

 

 

 

소스 코드 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
public class Main {
    private static int[] d = {1000, 100, 10, 1};
    private static boolean[] isNotPrime = new boolean[10000];
    private static boolean[] discovered = new boolean[10000];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int T= Integer.parseInt(br.readLine());
 
        findPrimeNum();
 
        while( T-- > 0){// T가 양수일때 진행
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
 
            if(A==B){
                System.out.println(0);
                continue;
            }
 
            int ret = bfs(A,B);
 
            System.out.println(ret);
        }
 
    }
 
    private static 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();
                // 종료조건(내가 찾던 값을 찾으면, 지금까지 진행한 step변수 리턴
                if(u==B){
                    return step;
                }
                // u->자리수 분할
                int[] cihper = new int[4];
                for (int j = 0; j <4 ; j++) {
                    cihper[j] = u/d[j];
                    u %= d[j];
                }
                // 탐색
                for (int j = 0; j <4 ; j++) {
                    for (int k = 0; k <10 ; k++) {
                        cihper[j] = cihper[j] + 1 > 9 ? 0 : cihper[j]+1;
                        int nextNum = 0;
                        for (int l = 0; l <4 ; l++) {
                            // d배열은 각 자리수를 표현해주기 위해 만든 배열이다.
                            nextNum += cihper[l]*d[l];
                        }
                        // 만든 자리수가 1000미만, 이미 체크했던것인지, 소수인지 확인하기.
                        if (nextNum < 1000) continue;
                        if(discovered[nextNum]) continue;
                        if(isNotPrime[nextNum]) continue;
 
                        // 모든 조건이 맞으면 queue에 넣고, discovered 배열에도 true표시
                        queue.add(nextNum);
                        discovered[nextNum] = true;
                    }
                }
 
            }
        }
        return -1;
    }
 
 
    private static void findPrimeNum(){
        // 소수인지 판별
        for (int i = 2; i <10000 ; i++) {
            if(isNotPrime[i]) continue;
            for (int j = 2; j*i <10000 ; j++) {
                isNotPrime[i*j] = true;
            }
        }
    }
}
 
 

 

 

결과 

저작자표시