"깊이 우선 탐색(DFS)"와 "너비 우선 탐색(BFS)" 알고리즘에 대해 알아보자!

🕸️ 그래프 탐색

하나의 정점(node)에서 시작하여 차례대로 모든 정점(node)를 한 번씩 방문하는 것

• 깊이 우선 탐색 DFS
• 너비 우선 탐색 BFS

✔️ 깊이 우선 탐색 DFS - Depth First Search

시작 node에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽히 탐색하는 방법
= 깊게(deep) 탐색 !

• 사용하는 경우 : 모든 노드를 방문하고 싶을 때!
• 구현 방법 : 재귀 함수 혹은 스택(stack)
  1. 탐색 시작 노드를 스택에 삽입 & 방문 처리
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있다면 그 노드를 스택에 넣고, 방문처리 (만약 방문하지 않은 인접한 노드가 없으면 스택에서 최상단 노드를 꺼냄)
  3. 2번 과정을 수행할 수 없을 때까지 반복

👍 DFS 이해를 돕는 백준 문제 + 문제 풀이

안전 영역(2468)

✔️ 너비 우선 탐색 BFS - Breadth First Search

시작 node에서 시작해서 인접한 node를 먼저 탐색하는 방법
= 넓게(wide) 탐색 !

• 사용하는 경우 : 두 node 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때
• 구현 방법 : 큐(queue)
  1. 탐색 시작 노드를 큐에 삽입 & 방문 처리
  2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리
  3. 2번 과정을 수행할 수 없을 때까지 반복

👍 BFS 이해를 돕는 백준 문제 + 문제 풀이

맥주 마시면서 걸어가기(9205)

🔥 DFS vs BFS

	DFS	BFS
구현(간단한 정도)	👍
검색 속도		👍
사용하는 경우	모든 노드에 방문	두 node 사이의 최단 거리 탐색

참고자료
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html