[자료구조] DFS, BFS

DFS와 BFS는 그래프(그 중에서 특히 트리)를 탐색하는 방법에서 나온 것이다.
그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말한다.
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

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

한 루트로 최대한 깊이 내려가 확인한 뒤, 더 이상 깊이 갈 곳이 없다면 다시 돌아가 다른 루트로 탐색한다.

 

DFS는 스택(Stack)이나 재귀함수로 구현한다. 구체적인 동작 과정은 다음과 같다.

• 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
• 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 그리고 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
• 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

---

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

루트 노드와 같은 거리에 있는 노드를 우선으로 방문하며 탐색한다.

큐(Queue) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
• 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.

---

DFS와 BFS는 각각 장단점이 있다.

DFS는 깊이 우선으로 탐색을 진행하기 때문에, 특정 경로를 찾거나, 그래프의 모든 노드를 방문하는 데 유용하다.

반면, BFS는 너비 우선으로 탐색을 진행하기 때문에, 최단 경로를 찾는 데 유용하다.