깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)에 대해 알아보기

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘 중 가장 기본적인 기법이다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성되며, 두 탐색 알고리즘은 서로 다른 방식으로 그래프의 정점을 탐색한다.

---

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

특징

• DFS는 가장 깊은 경로를 우선적으로 탐색하는 방식이다. 재귀 호출을 사용하거나 스택 자료구조를 이용하여 구현할 수 있다.
• DFS는 특정 조건을 만족하는 경로를 찾거나, 모든 경로를 탐색하는 데 유용하다.

동작 방식

1. 시작 정점에서 출발하여 한 방향으로 끝까지 탐색.
2. 더 이상 탐색할 정점이 없으면, 직전의 정점으로 돌아가 다른 방향 탐색.
3. 이를 반복하며 모든 정점을 방문.

구현 방식

• 재귀: 함수 호출을 이용하여 자연스럽게 스택 구조를 사용.
• 스택: 명시적으로 스택 자료구조를 사용.

---

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

특징

• BFS는 가까운 정점부터 탐색하는 방식이다. 큐(Queue) 자료구조를 이용하여 구현한다.
• BFS는 최단 경로를 찾거나, 정점 간의 관계를 파악하는 데 효과적이다.

동작 방식

1. 시작 정점을 큐에 넣고 방문.
2. 큐에서 정점을 꺼내 그 정점에 연결된 모든 정점을 큐에 추가.
3. 이를 반복하며 모든 정점을 방문.

구현 방식

• 큐: FIFO(First-In-First-Out) 구조를 사용하여 순차적으로 탐색.

---

DFS와 BFS의 비교

특징	DFS	BFS
탐색 우선순위	깊이 우선	너비 우선
사용 자료구조	스택(재귀 포함)	큐
적합한 문제 유형	경로 탐색, 백트래킹	최단 경로, 관계 탐색
메모리 사용	방문 경로 스택 크기에 따라 증가	탐색 너비에 따라 증가