[BFS, DFS]

모든 영역을 전체 탐색하는 방법

• 너비 우선 (BFS) vs 깊이 우선 (DFS)
• 별표 3개!!!

BFS (Breadth-First Search, 너비 우선 탐색)

• 루트 노드에서 가까운 노드들 부터 검색
• 최단 거리를 찾아내고 싶을 때 사용
• 재귀적 X
• 어떤 노드를 방문하였는지 체크해야 함 -> 안 하는 경우 무한루프
• 큐를 이용하여 구현. 큐에 방문할 노드를 하나하나 넣어두며 진행.
• 시간 복잡도 : O(N+E) [리스트], O(N^2) [행렬]

DFS (Depth-First Search, 깊이 우선 탐색)

• 루트 노드에서 관련 분기들을 탐색 후 다음 분기로 이동
• 모든 노드를 방문하고 싶을 때 사용
• 재귀적 O
• 어떤 노드를 방문하였는지 체크해야 함 -> 안 하는 경우 무한루프
• 스택을 이용하여 구현. 스택에 방문할 노드를 하나하나 넣어두며 진행.
• 시간 복잡도 : O(N+E) [리스트], O(N^2) [행렬]

같이 볼 예제

• BFS
• 미로 탐색

- DFS - [바이러스](https://www.acmicpc.net/problem/2606)

참고 문제

• 백준 단계 "DFS와 BFS"