613 BFS & DFS
| source | |
| type | 📌 개발노트 |
| parent_topic | 600-알고리즘 & 코딩테스트 |
| types | 학습 이론 |
| tags |
알아야할 libfrom collections import deque
DFS
한쪽경로의 끝을 확인할때 쓰임, 나는 이게 어떤 뭉탱이랑 구별되는지 같은거에 주로 썼음
- 스택(재귀)로 구현
- 재귀도 스택형식임
- 그래프로 눈에 보이는건 deque으로 처리할 만함
- 방문처리
- 백트래킹 : 방문처리후 돌고 방문처리를 다시 안함
- 걍 다도는 것
BFS
최단거리 구할 때(제일 먼저 push되는게 최단거리) / 같은 깊이를 비교할때 / 어떤 턴마다 확장되는 문제에서 많이 쓰였음
- 큐를 이용하여 구현
- while과함께하여 큐가 빌 때까지 도는게 일반적