[BOJ] - 신기한 소수/2023번 (JAVA)

[BOJ] - 신기한 소수/2023번 (JAVA)

---

1. 문제 접근

DFS의 개념을 사용해 구현하는 문제다.

그래프가 아닌 문제에대해 DFS를 적용하는 문제는 처음이라 재미있게 풀었다.

먼저 N자리 수에 대해 앞에서부터 소수판별을 하면된다.

이후 DFS를 통해 자리수를 늘려가며 해당 숫자가 소수인지 판별하는 것을 반복하면 된다.

DFS의 탈출조건은 주어진 자리수를 만족하는 것이다.

추가적으로 소수판별 알고리즘에서 브루트포스 방식의 판별을 사용할 경우, 대략 1,200ms의 실행시간이 걸리지만, 해당 수의 제곱근까지로 범위를 제한하면 실행시간이 1/10까지 단축시킬 수 있다.

---

2. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    public static int N;
    public static LinkedList<Integer> ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        ans = new LinkedList<>();

        for (int i = 2; i < 10; ++i) {
            if (isPrimeNumber(i)) {
                DFS(i, 1);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Integer ans : ans) {
            sb.append(ans);
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static void DFS(int num, int currDigitCnt) {
        if (currDigitCnt == N) {
            ans.add(num);
            return;
        }
        for (int nextDigit = 1; nextDigit < 10; ++nextDigit) {
            int n = num * 10 + nextDigit;
            if (isPrimeNumber(n)) {
                DFS(n, currDigitCnt + 1);
            }
        }
    }

    public static boolean isPrimeNumber(int num) {
        if (num == 1) {
            return false;
        }
        int end = (int) Math.sqrt(num);
        for (int i = 1; i <= end; ++i) {
            if (i == 1) {
                continue;
            }
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}