[DFS] 백준 #2023 신기한 소수 찾기 - Python

📚 문제

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

2023번: 신기한 소수

 

💡 접근법

자릿수가 한 개인 소수(2, 3, 5, 7)부터 DFS 탐색을 시작한다.

소수에 10을 곱하고 0부터 9까지 더한 값이 소수인지 판별하는 과정을 반복한다.

이때 2의 배수를 더할 경우 무조건 소수가 아니므로 이를 제외하고 수행한다.

DFS란?
그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

💻 코드

1) 전체 코드

import sys
import math
sys.setrecursionlimit(10000)

N = int(sys.stdin.readline())


def is_prime(a):
    for i in range(2, int(math.sqrt(a)) + 1):
        if a % i == 0:
            return False
    return True


def DFS(x):
    if len(str(x)) == N:
        print(x)
    else:
        for i in range(1, 10, 2):
            if is_prime(x * 10 + i):
                DFS(x * 10 + i)


prime_num = [2, 3, 5, 7]
for p in prime_num:
    DFS(p)

 

2) 해설

(1) 패키지 Import

import sys
import math
sys.setrecursionlimit(10000)

파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리를 사용하였고,
소수를 구할 때 제곱근을 구하기 위해 math 라이브러리를 사용하였다.

또한 파이썬의 재귀 최대 깊이의 기본 설정이 1,000회이므로 재귀의 최대 깊이를 10000으로 늘려주었다.

 

(2) 소수 판별 함수 구현

def is_prime(a):
    for i in range(2, int(math.sqrt(a)) + 1):
        if a % i == 0:
            return False
    return True

자기 자신의 제곱근(루트)까지만 확인하여 소수를 판별한다.

 

(3) DFS 구현

def DFS(x):
    if len(str(x)) == N:
        print(x)
    else:
        for i in range(1, 10, 2):
            if is_prime(x * 10 + i):
                DFS(x * 10 + i)

만약 N자리일 경우 값을 출력한다. 이때 문제의 요구대로 오름차순 정렬되어 출력된다.

소수에 10을 곱하고 0부터 9까지의 값을 더하여 이 값이 소수인지 판별하고, 소수일 경우 재귀 방식으로 DFS를 수행한다.

이때 소수 * 10에 2의 배수를 더할 경우엔 무조건 소수가 아니므로 이 경우는 제외한다.

 

(4) 출력하기

prime_num = [2, 3, 5, 7]
for p in prime_num:
    DFS(p)

자릿수가 한 개인 소수에 대해 DFS를 수행한다.

 

✅ 정답 확인

 

---

 

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!

읽어주셔서 감사합니다^.^