self.winter.(09-4). DFS (깊이 우선 탐색) 문제 _ 백준 2023, 백준 13023

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

https://chan4im.tistory.com/121

self.winter.(09-3). DFS (깊이 우선 탐색) 개념 _ 백준 11724(connected component)

 

 

🧐 백준 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)