알고리즘 풀이 - 백준 1963(소수 경로, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조
소수 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

4자리의 비밀번호를 A → B로 바꾸고 싶을 때, 4자리 중 1자리만 바꿀 수 있는 경우, 그 1자리를 바꿀 때도 전체 값이 소수가 되는 경우만 가능할 때, 몇 번의 변경으로 비밀번호를 바꿀 수 있는지 확인하는 문제

 

 

2. 풀이

 

소수를 구하는 문제 관련 포스팅은 이미 이전에 진행한 적 있다. 상단의 링크를 참조

 

여기서는 가장 빠른 에라토스테네스의 체를 이용하여 1000~9999까지 모든 소수를 미리 구하고 시작하였다.

그리고 1, 10, 100, 1000의 자리의 모든 숫자를 1씩 변경해가며 소수인 경우를 모두 체크하는 BFS 코드를 작성하여 문제를 해결하였다.

각 자리수의 숫자를 1씩 바꾸며 탐색하는 부분이 조금 까다로웠는데 아래의 코드에 주석을 잘 달아놓았으므로 참고하면 이해할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

import java.io.*;
import java.util.*;

public class Main{
    static boolean[] notPrime = new boolean[10000];
    public static void main(String[] args) throws IOException{
        
        // 소수들을 모두 표시한다.
        getPrimes();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        // 테스트 케이스 수행
        while(t-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            int ans = bfs(a, b);
            if(ans == -1){
                sb.append("Impossible").append("\n");
            } else {
                sb.append(ans).append("\n");
            }
        }
        
        System.out.println(sb);
        br.close();
    }
    
    // 에라토스테네스의 체를 이용해 2~9999까지의 숫자 중 소수가 아닌 것을 체크
    private static void getPrimes(){

        // 2부터 시작하여 9999까지 소수를 체크한다.
        for(int i=2; i < 10000; i++){
            // 숫자 i가 소수라면
            if(!notPrime[i]){
                for(int j=i*i; j < 10000; j += i){
                    notPrime[j] = true;
                }
            }
        }
    }
    
    // BFS를 통해 1자리씩 변경하며 소수를 찾는 메소드
    private static int bfs(int a, int b){
        boolean[] visited = new boolean[10000];
        Queue<Num> q = new LinkedList<>();
        visited[a] = true;
        q.offer(new Num(a, 0));
        
        while(!q.isEmpty()){
            Num c = q.poll();
            if(c.n == b) return c.t;
            
            int temp = c.n;
            for(int i=3; i >= 0; i--){
                // 현재 자리수의 값을 찾는다.
                // 예를 들어 9642 에서 가장 좌측의 숫자를 바꾸는 경우
                // d=9000이 된다.
                int d = temp / (int)Math.pow(10, i) * (int)Math.pow(10, i);
                
                // 현재 자리수 만큼 더해가며 체크하기 위해 더할 값을 찾는다.
                // 10의 자리 숫자가 바뀐다면 10씩 더해야 하므로 10^1이 되어 10,
                // 100의 자리 숫자가 바뀐다면 100씩 더해야 하므로 10^2이 되어 100
                int plus = (int)Math.pow(10, i);
                
                // 바꿀 위치의 숫자를 0으로 만들고 1씩 변경해가며 탐색한다.
                for(int j=c.n-d; j <= c.n-d+(plus*9); j += plus){
                
                    // 범위를 벗어났거나 이미 체크 완료된 숫자거나, 소수가 아니면 넘어간다.
                    if(j < 1000 || j > 9999 || visited[j] || notPrime[j]) continue;
                    
                    // 원하는 숫자에 도달한 경우 반환
                    if(j == b) return c.t+1;
                    q.offer(new Num(j, c.t+1));
                    visited[j] = true;
                }
                temp -= d;
            }
        }
        return -1;
    }
}

class Num{
    int n;  // 현재 숫자
    int t;  // 값을 바꾼 횟수
    public Num(int n, int t){
        this.n=n;
        this.t=t;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.