탐색 알고리즘 문제 풀어보기 1(백준 2023번 신기한 소수 찾기)

DFS와 BFS가 무엇인지를 알았으니 실제 적용해 문제를 풀어보도록 하겠다. 이번에 풀 문제는 백준2023번 신기한 소수 찾기이다. https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

이 문제는 숫자의 자릿수를 입력받으면 해당 자릿수의 숫자들 중 왼쪽부터 숫자를 증가시키며 모두 소수인 숫자를 찾는 것이다. 이 문제를 보고 가장 먼저 떠올린 생각은 앞에서부터 하나씩 숫자를 늘려가며 검사하면 되겠다는 생각이었고 그러기 위해서는 탐색방법을 사용해야 했다. 맨 앞의 숫자는 2,3,5,7만이 가능하므로 해당 숫자들로 탐색을 시작하고 자릿수가 최대가 될 때까지 검사를 하면 되겠다고 생각했다. 먼저 DFS로 구현한 코드를 보자.

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

public class Main {
    static Integer N;
    public static void main(String[] args){
        Scanner scn = new Scanner(System.in);
        N = scn.nextInt();
        DFS(2,1);
        DFS(3,1);
        DFS(5,1);
        DFS(7,1);
    }
    static boolean check(int num){
        if(num==1) return false;
        else if(num==2) return true;
        else if(num==3) return true;
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0) return false;
        }
        return true;
    }
    static void DFS(int num, int n){
        if(!check(num) || n>N) return;
        if(n==N){
            System.out.println(num);
            return;
        }
        for(int i=1;i<10;i=i+2){
            DFS(num*10+i,n+1);
        }
    }
}

DFS함수는 최초 왼쪽 숫자와 현재 자릿수를 입력받게 하여 깊이가 증가할 때마다 자릿수를 하나씩 증가시켜 최대자릿수가 되면 출력하고 리턴하게 하였다. 숫자의 자릿수를 증가시키는 것은 현재숫자에 10을 곱한 후 1부터 9까지 홀수만 더해주는 것으로 구현하였다. 끝자리가 짝수면 무조건 소수가 아니니 2씩 증가하도록 해주었다. 그렇게 DFS를 하면서 check함수로 해당 숫자가 소수가 맞는지 여부를 확인해 주었다. check함수는 소수인지 판별하려는 숫자의 제곱근까지만 검사하여 최소로 검사하게 하였다.

다음 코드는 BFS로 문제를 푼 것이다.

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

public class Main {
    public static void main(String[] args){
        Scanner scn = new Scanner(System.in);
        int N = scn.nextInt();
        BFS(2,N);
        BFS(3,N);
        BFS(5,N);
        BFS(7,N);
    }
    static boolean check(int num){
        if(num==1) return false;
        else if(num==2) return true;
        else if(num==3) return true;
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0) return false;
        }
        return true;
    }
    static void BFS(int num, int N){
        Queue<Integer> queue = new LinkedList<>();
        double n = Math.pow(10,N-1);
        queue.add(num);
        while(!queue.isEmpty()){
            int number = queue.poll();
            if(number/n<10 && number/n>=1){
                System.out.println(number);
                continue;
            }
            for(int i=1;i<10;i=i+2){
                int a = number*10 + i;
                if(check(a)){
                    queue.add(a);
                }
            }
        }
    }
}

check함수는 동일하고 함수에 매개변수로 시작 자릿수를 주는 것이 아니라 최대 자릿수를 주었다. 큐를 선언하여 탐색을 하다가 소수가 맞으면 큐에 넣어 그다음 자릿수를 탐색하도록 해주었고 해당 숫자를 10^(N-1)로 나눈 몫이 1 이상 10 미만이어야 N자릿수가 된 것이므로 그때 출력을 하고 큐에 넣는 과정을 생략하기 위해 continue구문을 써주었다. DFS와 마찬가지로 끝자리수는 홀수만 더해서 소수가 맞으면 큐에 넣어주는 방식으로 구현하였다.

같은 문제를 DFS와 BFS로 모두 풀어보니 확실히 다른 느낌이 든다. 이 문제에서는 DFS가 구현하기 더 쉬웠던 것 같다. 문제를 처음 분석할 때 어떤 방식이 더 구현하기 쉬울지 고민해 보는 시간이 확실히 필요함을 알 수 있었다. 다음 포스팅에서는 또 다른 탐색문제를 풀어보도록 하겠다.