그래프 탐색 알고리즘: DFS/BFS
- 탐색이란, 많은 양의 데이터 중 원하는 데이터를 찾는 과정
- 대표적인 그래프 탐색 알고리즘 -> DFS/BFS
- DFS/BFS는 매우 자주 나오는 유형 (반드시 숙지!!)
* 알아야 할 자료 구조 - Stack, Queue
* Stack
- 입구/출구 동일한 형태(먼저 들어 온 데이터가 나중에 나가는 형식)
- 쌓아 올린 책과 같음
- append(value), pop(), list_stack[::-1]
* Queue
- 먼저 들어온 데이터가 먼저 나가는 형식
- 입구/출구 모두 뚫려있는 터널과 같은 형태로 시각화
- 시간복잡도 때문에 리스트 사용 x, 위치를 변경하기 때문에 O(k)만큼 더 요구됨
- append(value), popleft(), reverse() - 역순 출력
from collections import deque
* 재귀함수(recursive function)
- 자기 자신을 다시 호출하는 함수
- 반드시 재귀함수의 종료조건을 반드시 명시해야함
- 관련문제: 최대공약수 구하기
dfs는 깊이 우선, bfs는 너비 우선 이란 말이 있으면 좀더 좋을 거 같네요