[220601][스터디준비] - DFS

DFS와 BFS란?

트리와 그래프 탐색하는 방법.
- 즉, 하나의 정점으로부터 시작해 순서대로 모든 정점을 한번씩 방문하는 방법!
- “그래프 탐색 알고리즘”
- 탐색 ex : 데이터베이스 안의 수많은 자료 중에서 원하는 자료 찾는 것
DFS : Depth First Search. 깊이 우선 탐색 (수직적)
- 시작 노드로부터 해당 분기를 완벽하게 모두 탐색 후 다음 분기로 넘어가는 방법
- 장점
  - 현 경로상의 노드들을 기억하므로 적은 메모리 사용 (공간 복잡도 good)
  - 목표 노드가 깊은 단계에 있을 경우엔 BFS보다 빠름
- 단점
  - 검색 속도는 일반적으로 BFS에 비해 느림 (해가 없는 분기더라도 끝까지 탐색하므로)
    - 따라서 임계 깊이까지만 탐색하도록 미리 지정
  - DFS를 통해 얻어진 해가 최단 경로라는 보장은 X (just 해에 도착하면 탐색 종료)
- 스택(LIFO) or 재귀함수로 구현
  - 재귀가 더 간결
```
visited = [] # 이전에 방문했던 노드 리스트 (1차원)
stack = [] # 방문해야 하는 노드 리스트
```
BFS : Breadth First Search. 너비 우선 탐색 (수평적)
- 시작 노드로부터 가까운 노드를 먼저 탐색하는 방법
- 주로 두 노드 사이의 **최단 경로(거리)**를 찾고 싶을 때 이용
- 장점
  - 여러가지 답이 있어도 모두 최단 경로를 보장 O
- 단점
  - 경로가 매우 길 경우, 많은 메모리 필요 (공간 복잡도 bad)
- **큐(FIFO)**로 구현
  - cf. 큐를 list로 사용하지 않는 이유? ⇒ 시간 복잡도 차이
    - list.pop(0) ⇒ O(n)
    - deque.pop() ⇒ O(1)
```
from collections import deque

visited = [] # 이전에 방문했던 노드 리스트 (1차원)
queue = deque() # 큐 (덱, 디큐)
```

Untitled

DFS(stack 과정) : 1 → (1 pop) → 8, 7, 2 → 1, 8, 7 (2 pop)→ 1, 8, 7, 6, 3 → 1, 8, 7, 6 (3 pop) → …
BFS(queue 과정) : 1 → (1 popleft) → 4, 3, 2 → 3, 2 (4 popleft) → 2 (3 popleft) → (2 ~) → 6, 5 → …
cf. 비교 요약

Untitled