탐색: 많은 양의 데이터 중 원하는 데이터를 찾는 과정
DFS, BFS: 대표적인 그래프 탐색 알고리즘으로, 코딩 테스트에 매우 자주 나오는 유형

관련 자료구조

Stack(스택)

먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
입구와 출구가 동일한 형태로 스택을 시각화할 수 있음
ex.)
비유: 나중에 들어온 것이 먼저 나간다는 점에서 박스 쌓기와 같다고 이해할 수 있음

• 파이썬: 리스트로 스택 구현 가능
  리스트를 이용한 방법은 시간 복잡도 O(1)으로 효율적이기 때문에, 별도의 라이브러리 없이 리스트로 구현

stack = []
stack.append(5)
stack.append(2)
...
stack.pop()
stack.append(1)
stack.pop()
...

print(stack[::-1] # 최상단(나중에 들어간 순) 원소부터 출력
print(stack) # 최하단(먼저 들어간 순) 원소부터 출력

Queue(큐)

먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있음
편의점 우유 매대 선입선출로 줄세우는 것으로 비유 가능

• 파이썬: deque(덱) 라이브러리를 사용하여 구현 가능
  리스트로도 구현 가능하지만 리스트보다 deque 라이브러리가 시간복잡도 면에서 훨씬 효율적임(시간 복잡도 = O(1))

from collections import deque
queue = deque()
queue.append(5) # 값 추가
queue.popleft() # 먼저 들어간 값 제거
...

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 큐 안의 값들 순서 뒤집기
print(queue) # 나중에 들어온 값부터 출력

재귀 함수(Recursive Function)

함수 안에서 자기자신(함수)을 다시 호출하는 함수
메모리 때문에, 파이썬에서는 재귀적으로 함수를 호출하는 depth에 제한을 둠
문제 풀이에서 재귀 함수를 사용할 때는 재귀 함수의 종료조건을 반드시 명시하여 무한 루프를 방지해야 함
재귀 함수를 활용하면 코드를 보다 간결하게 작성할 수 있지만(ex. DFS), 이로 인해 오히려 가독성이 떨어질 수도 있으므로 신중하게 사용해야 함
반복문 <-> 재귀 함수 : 모든 재귀 함수는 반복문으로 똑같이 구현 가능. 반복문이 유리한 경우도 있고 재귀함수가 유리한 경우도 있음
스택을 구현할 때 함수를 연속적으로 호출하면 메모리 내부의 스택 프레임에 쌓이므로, 성능 개선을 위해 스택을 사용할 깨 스택 라이브러리 대신 재귀함수를 이용하기도 함
ex.) 기본 예시

def recursive_function(i):
	# 종료 조건 (100번째 호출에서 종료되도록 하는 조건)
    if i == 100:
    	return
	print(f'{i}번째 재귀함수에서 {i+1}번째 재귀 함수를 호출합니다.')
 	recursive_function(i+1)
    print(f'{i}번째 재귀 함수를 종료합니다.')
recursive_function(1) # 종료 조건까지 '재귀 함수를 호출합니다.' 출력

• 팩토리얼(!) 구현 예시
  반복문으로도 구현할 수 있으나, 재귀 함수를 이용하면 보다 간결한 코드 작성 가능
  
• 최대공약수(GCD) 계산(유클리드 호제법)
  - 유클리드 호제법: 큰 수와 작은 수의 최대공약수 = 작은 수와 큰 수를 작은 수로 나눈 나머지의 최대공약수
  재귀함수를 통해 최대공약수가 나올 때까지 계속 나누면 최대공약수를 구할 수 있음
  

# a>b라고 가정
def gcd(a,b):
	if a % b == 0:
    	return b
    else:
    	return gcd(b, a%b)

print(gcd(192,162)) # 6

DFS(Depth-First Search)

깊이 우선 탐색(그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘)
그래프에서 최대한 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료구조 or 재귀 함수를 이용하여 풀이 가능

• 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
• 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리
• 3. 더 이상 2.를 수행할 수 없을 때까지 반복

# 각 노드가 연결된 정보를 표현한 2차원 리스트(예시)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]
# 각 노드가 방문되었는지 여부를 표현한 1차원 리스트
visited = [False] * 9

# dfs 함수
def dfs(graph, v, visited):
	visited[v] = True
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
# dfs 함수 호출(graph의 첫 번째 노드부터 깊이 우선하여 모두 탐색)
dfs(graph, 1, visited)

BFS(Breadth-First Search)

너비 우선 탐색(그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘)
시작 노드로부터 가까운 노드부터 우선 방문
큐 자료구조(deque 라이브러리)를 이용하여 풀이

# 각 노드가 연결된 정보를 표현한 2차원 리스트(예시)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
]
# 각 노드가 방문되었는지 여부를 표현한 1차원 리스트
visited = [False] * 9

# bfs 함수
from collections import deque


def bfs(graph, start, visited):
	queue = deque([start])
    visited(start) = True
    
    while queue:
    	v = queue.popleft()
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
            
# dfs 함수 호출(graph의 첫 번째 노드부터 깊이 우선하여 모두 탐색)
bfs(graph, 1, visited)