• 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
• DFS & BFS: 대표적인 그래프 탐색 알고리즘
• DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형 → 반드시 숙지!

DFS

• 다음 분기(브랜치)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식
• 예: 미로찾기
• 모든 노드 방문 시 유용
• BFS 보다 간단하지만 속도는 느림
• 스택 또는 재귀 함수로 구현

BFS

• 루트노트에서 시작해 인접한 노드를 먼저 탐색
• 예: 두 노드 사이의 최단 경로 찾기
• 큐를 이용해서 구현

스택 자료구조

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조

• 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있음

  예) 박스 쌓기

• 파이썬에서 이러한 스택 자료구조를 이용하는 방법 - 리스트(라이브러리 필요 없음)

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) # [1,3,2,5] - 최상단 원소부터 출력
print(stack) # [5,2,3,1] - 최하단 원소부터 출력

큐 자료구조

• 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조
• 큐는 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화 할 수 있다

• 파이썬에서 이러한 큐 자료구조를 이용하는 방법 - deque 라이브러리 사용
• 큐 자료구조를 이용할 때 라이브러리 없이 리스트를 통해 기능적으로 구현을 할 수 있긴 하지만 시간복잡도가 더 높아져 비효율적임

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # deque([3,7,1,4]) - 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # deque([4,1,7,3]) - 나중에 들어온 원소부터 출력