반응형
12-24 07:02
Today
Total
«   2024/12   »
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
관리 메뉴

개발하는 고라니

[백준] 1963번 : 소수 경로 본문

Programming/백준

[백준] 1963번 : 소수 경로

조용한고라니 2021. 3. 12. 03:16
반응형
 

1963번: 소수 경로

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금

www.acmicpc.net


[BFS]

 

4자리 이면서 소수인 숫자를 한 자리씩 바꾸는데, 바꿔서 완성된 4자리 수도 소수이어야 한다. 그래서 목표 소수까지 가야하는데, 한 자리씩 어떻게 바꿀 것 인가에 대한 방법은 다양할 것이다.

 

나는 문자열로 변환하여 풀었다. 예를 들어 1033이라는 수가 있으면, 이를 문자열로 변환하고 1000의 자리, 100의 자리, 10의 자리, 1의 자리에 각각 0~9를 대입하며

(1) 방문했었는지 ?

(2) 4자리 숫자인지 ?

(3) 소수인지 ?

를 따져서 해당 조건을 모두 충족하면 Queue에 넣어 BFS를 수행하였다

 

소수를 판별하는 알고리즘은 숫자 x가 주어졌을 때 2 ~ x의 제곱근까지 나머지 연산을 하며 약수가 있는지 체크하는 것을 사용했다.

 

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

public class Main {

    static boolean[] visit;
    static String[] nums = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
    static int[] move;
    
    static boolean isPrime(int x){

        for(int i=2; i<=Math.sqrt(x); i++)
            if(x % i == 0)
                return true;

        return false;
    }

    static void BFS(int s, int e){

        Queue<Integer> Q = new LinkedList<>();
        visit[s] = true;
        move[s] = 0;

        Q.add(s);

        while(!Q.isEmpty()){
            int cur = Q.poll();

            for(int a=0; a<10; a++)
                for(int b=0; b<4; b++){

                    StringBuilder sb = new StringBuilder(Integer.toString(cur));

                    sb.replace(b, b+1, nums[a]);

                    int next = Integer.parseInt(sb.toString());

                    if(next < 1000 || next > 9999 || visit[next] || isPrime(next)) continue;

                    visit[next] = true;
                    move[next] = move[cur] + 1;
                    if(next == e) return;

                    Q.add(next);
                }
        }
    }

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

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

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

        for(int i=0; i<t; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            visit = new boolean[10000];
            move = new int[10000];
            Arrays.fill(move, -1);

            BFS(a, b);

            System.out.println(move[b] == -1? "impossible" : move[b]);
        }
    }
}

.

반응형

'Programming > 백준' 카테고리의 다른 글

[백준] 1654번 : 랜선 자르기  (0) 2021.03.13
[백준] 10815번 : 숫자 카드  (0) 2021.03.12
[백준] 16946번 : 벽 부수고 이동하기 4  (0) 2021.03.10
[백준] 9328번 : 열쇠  (0) 2021.03.09
[백준] 1525번 : 퍼즐  (0) 2021.03.07
Comments