this.code();

🧐 깊이 우선 탐색, DFS (Depth First Search)

https://chan4im.tistory.com/121

🧐 백준 2023 (DFS)   Gold V 

🤔 Algorithm 과정 
1. 한자리소수 -> 이 한자리 소수에서 파생되어 나온 두자리소수 -> ... 의 반복이므로
2. 한자리 소수는 [2, 3, 5, 7]이다.
3. 여기서 파생되는 소수는 다음과 같다.
[2] - 23, 29
[3] - 31, 37
[5] - 53, 59
[7] - 71, 73, 79
위 과정을 계속 반복하여 입력된 자리수에 맞는 출력을 진행해주면 된다.
이는 재귀를 이용한 DFS를 통해 해결할 수 있으며 아래 그림을 통해 간단히 도식화 하였다.

🤫  solution_2023 (시간초과)

import sys, math
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N = int(input())

dec = [i for i in range(2, 8*10**(N))]
dec_front = []
for i in range(2, int(math.sqrt(10**(N+1))) + 1):
    if i in dec:
        dec_front.append(i)
    dec = [j for j in dec if j % i != 0]
decimal = dec_front + dec

single_decimal = [2, 3, 5, 7]

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

for i in single_decimal:
    DFS(i)

🤫  solution_2023

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N = int(input())
single_decimal = [2, 3, 5, 7]

def decimal(num):
    for i in range(2, num//2 + 1):
        if num % i == 0:
            return False
    return True

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

for i in single_decimal:
    DFS(i)

cf. // 는 정수형 나눗셈이다. 

🧐 백준 13023 (DFS)   Gold V 

🤔 Algorithm 과정 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다.
3. DFS를 수행하는데, 아래와 같이 진행한다.
4. 최종적으로 DFS의 재귀 횟수가 5회 이상이면 되므로 5회가 된 순간이 바로 임계점이다.
5. 따라서 재귀횟수가 5회면 바로 1을 출력하고 5회 미만이라면 0을 출력한다.

🤫  solution_13023

# 백준 11724
# 친구 관계 5개를 찾는 문제 = 재귀 깊이가 5번 이상이면 된다.
import sys
input = sys.stdin.readline

V, m = map(int, input().split())
vertex = [[] for _ in range(V+1)]

# 방문 리스트 생성
visit_list = [False] * (V+1)

for _ in range(m):
    u, v = map(int, input().split())
    vertex[u].append(v)
    vertex[v].append(u)
# print(vertex) => [[1], [0, 2], [1, 3], [2, 4], [3], []]
# 인접 리스트 생성       [0]   [1]     [2]     [3]    [4]

threshold = False
def DFS(curr_vertex, depth):
    global threshold
    if depth == 5:
        threshold = True
        return
    visit_list[curr_vertex] = True
    for i in vertex[curr_vertex]:
        if not visit_list[i]:
            DFS(i, depth+1)
    visit_list[curr_vertex] = False

for i in range(V):
    DFS(i, 1)
    if threshold:
        break

if threshold:
    print(1)
else:
    print(0)

🧐 백준 11724 (Connected Component)

- connected component 즉, 연결요소는 다음과 같은 조건에서 성립한다.

• 연결요소에 속한 모든 정점(vertex)을 연결하는 간선(edge)가 있어야 한다.
• 또 다른 연결요소에 속한 정점(vertex)과 연결하는 간선(edge)이 있으면 안된다.

🤔 Algorithm 과정 
0.  노드의 최대 개수가 1000이므로 시간복잡도 n^2이하의 알고리즘을 모두 사용할 수 있다.
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다.
3. DFS를 수행하는데, 아래와 같이 진행한다.

🤫  solution_11724

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

V, E = map(int, input().split())
CC = [[] for _ in range(V+1)]  # [[], [], [], [], [], [], []]
visit_list = [False] * (V+1)

for _ in range(E):
    u, v = map(int, input().split())
    # 양방향 간선이므로 양쪽에 정점 더하기.
    CC[u].append(v)
    CC[v].append(u)
# print(CC) => [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]
# 인접리스트 생성         [1]     [2]   [3]    [4]     [5]   [6]


def DFS(v):
    visit_list[v] = True
    for i in CC[v]:
        if not visit_list[i]: # 연결요소가 방문리스트에 F로 되어있으면 True로 고치기 위한 재귀
            DFS(i)

cnt = 0
for i in range(1, V+1):
    if not visit_list[i]:  # 1 2 3 4 5 6의 방문리스트에 대해 방문한적이 없다면
        cnt += 1
        DFS(i)

print(cnt)