[JAVA][Baekjoon] 2023번 신기한 소수

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

---

📌 접근 방식

DFS(깊이 우선 탐색) 을 사용했다!

 

• 한 자리씩 숫자를 추가하면서 신기한 소수를 탐색하기에 적합하기 때문
• 숫자를 추가할 때마다 소수인지 확인하고, 조건에 맞지 않으면 더 이상 탐색하지 않는다.
  이렇게 하면 불필요한 연산을 줄일 수 있음! 🛠
• example) 시작 숫자가 7이라면
  1️⃣ 7 → 소수 맞네! 더 탐색!
  2️⃣ 73 → 소수네? 한 자리 더 추가!
  3️⃣ 733 → 오, 또 소수야! 더 가보자!
  4️⃣ 7331 → 완성! 신기한 소수 발견! 🎉

 

[알고리즘] 깊이 우선 탐색 : DFS(Depth-First-Search)

---

✅ PASS CODE

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

public class Main {
    public static int N;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        DFS(2, 1);
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);
    }
    public static void DFS(int u, int v) {
        if(v == N) {
            if(isPrime(u)) {
                System.out.println(u);
            }
            return;
        }
        for(int i=1; i<10; i++) {
            if(i%2 == 0) {
                continue;
            }
            if(isPrime(u * 10 + i)) {
                DFS(u * 10 + i, v+1);
            }
        }
    }
    public static boolean isPrime(int num) {
        for(int i=2; i<=num/2; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

🔑 핵심 포인트

1️⃣ u * 10 + i 로 소수 숫자를 늘려나감 예: 7 → 73 → 733.
2️⃣ 숫자가 소수인지 확인 후, 소수면 더 탐색한다.
3️⃣ 조건이 맞지 않으면 바로 return

 

⚡ 개선 가능점

num / 2 대신 Math.sqrt(num)을 사용할 수도 있을 것 같다!

---

반응형

😊 느낀 점

이 문제를 풀면서 DFS(깊이 우선 탐색) 을 활용해 효율적으로 숫자를 탐색하는 방법에 대해 깊이 생각해볼 수 있었다. 이렇게 조건을 미리 걸러내는 방식은 불필요한 연산을 줄이는 데 큰 도움이 되었고, 알고리즘의 효율성을 높이는 데도 중요한 요소임을 깨달았다!

처음에는 소수를 하나하나 비교하면서 어느 세월에 구하지..? 싶었는데 DFS를 이용하니까 훨씬 빠르게 탐색할 수 있었다! 덕분에 코드도 간결하게 구현할 수 있었고, 문제 해결 과정이 훨씬 재미있게 느껴졌다 👋🏻