this.code();

BFS(G, start_v)
    let Q be a queue
    mark start_v as visited
    Q.enqueue(start_v)
    while Q is not empty do
        v := Q.dequeue()
        if v is the goal then
            return v
        for all edges from v to w in G.adjacentEdges(v) do
            if w is not marked as visited then
                label w as visited
                w.parent := v
                Q.euqueue(w)

def bfs(start_v):
    visited = [start_v]
    Q = deque([start_v])
    while Q:
        v = Q.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.append(w)
                Q.append(w)

    return visited

🧐 백준 1260 (DFS와  BFS)

🤔 Algorithm 과정_ DFS 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다.
3. 재귀를 이용한 DFS를 수행하는데, 아래와 같이 진행한다.

🤔 Algorithm 과정_ BFS 
1. 그래프를 인접리스트로 저장한다. (무방향 그래프이기에 양쪽방향으로 간선을 모두 저장한다.)
2. 방문리스트를 모두 False로 초기화한다. (이때, 위의 DFS에서 사용했기에 초기화를 반드시 해줘야 한다!)
3. BFS를 수행하는데, 아래와 같이 진행한다.

이를 풀이하면 다음과 같다.

1. 큐 자료구조에 starting_vertex 삽입
visit_list에 현재 vertex 기록

2. while (큐가 빌 때 까지):
	큐에서 vertex를 가져와 출력
    현재 vertex의 연결vertex 중 미방문 vertex를 큐에 삽입(append)
    방문리스트에 기록

🤫  solution_1260

import sys
input = sys.stdin.readline

V, E, starting_vertex = map(int, input().split())

# graph라는 인접리스트 생성
#         [1]      [2]     [3]       [4]
# [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3], []]
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 정점에 우선순위가 부여되었으므로 정렬
for i in range(V+1):
    graph[i].sort()

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

def DFS(v):
    print(v, end = " ")
    visit_list[v] = True
    for i in graph[v]:
        if not visit_list[i]:
            DFS(i)

from collections import deque
def BFS(v):
    queue = deque()
    queue.append(v)
    visit_list[v] = True
    while queue:
        curr_vertex = queue.popleft()
        print(curr_vertex, end = " ")
        for i in graph[curr_vertex]:
            if not visit_list[i]:
                visit_list[i] = True
                queue.append(i)


# DFS 출력
DFS(starting_vertex)
print()

visit_list = [False] * (V+1)    # 리스트 초기화
# BFS 출력
BFS(starting_vertex)

🧐 깊이 우선 탐색, 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)