[백준 2023] 신기한 소수 - 파이썬(Python) DFS 풀이

신기한 소수

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력 1

4

예제 출력 1

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

---

깊이 우선 탐색(DFS)

루트 노드(정점)에 연결된 여러 분기(루트와 연결된 정점들)가 있을 것입니다.

한 분기를 탐색하고 바로 다른 분기로 넘어가는것이 아니라, 한 분기에 대해서 모든 탐색을 끝내고, 다음 분기의 탐색을 시작하는 방법입니다.

그래서 넓게가 아닌 깊게 탐색한다고 하는 것입니다. 그렇기 때문에 미로 탐색 문제 등에 어울립니다.

 

아래는 DFS로 탐색하는 순서입니다. 정점에 쓰여져 있는 숫자는 n번째, 즉 순서를 의미합니다.

보시면 알겠지만 루트(1번)의 첫번째 분기(2번)에 대해서 모든 정점들을 차례대로 방문한 다음에 다음 분기(7번)으로 넘어가는것을 볼수 있습니다.

---

DFS 구현

• 스택(Stack) 자료 구조를 이용해서 구현
• 재귀호출을 이용해서 구현

재귀호출 자체가 스택 형식이기 때문에 재귀호출로도 구현할수 있는 것입니다.

---

파이썬 코드

한 자리 소수로 시작해서 두자리, 세자리 소수를 구하고 네자리를 구하는 방식으로 풀었습니다.

만약에 한자리가 2라면, 인접노드들을 두자리인 21 23 25 27 29 등등으로 생각하면 되므로 그래프 탐색 알고리즘을 이용했습니다.

사실 bfs , dfs 둘다 상관없는데, dfs 방식으로 구했습니다.

한자리 소수는 2,3,5,7이기 때문에 이 수들을 상위 노드로 dfs 탐색을 시작했습니다.

인접노드들은 이전노드에다가 홀수를 붙인 수인데, 붙였을때 소수가 되는 노드들만 골라서 탐색했습니다.

그렇게 탐색하다가 네자리 수일때(문자열 길이가 4) 그 수를 출력하고 탐색을 종료합니다.

#DFS
import sys
sys.setrecursionlimit(10000)
n = int(input())
def isPrime(num):
    for i in range(2, int(num**(1/2))+1):
        if num%i==0:
            return False
    return True

def dfs(number):
    if not isPrime(number):
        return
    if len(str(number)) == n:
        print(number)
    for i in range(1,10,2):
        dfs(number*10 + i)
    return

for i in [2,3,5,7]:
    dfs(i)