# [알고리즘] 탐색 알고리즘 - Dfs / Bfs

**탐색**이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 **DFS와** **BFS**를 꼽을 수 있다.

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1762686828725/a0f7a58e-e8ac-4409-90f1-347f070c9334.gif align="center")

DFS는 Depth - First Search, 깊이 우선 탐색이라고도 부르며, 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

그림에서와 같이 갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길로 돌아와 선택하지 않았던 노드를 방문하는 식으로 탐색한다. DFS는 스택(Stack) 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.

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

**※ DFS의 구현**

DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다.

실제로는 스택을 쓰지 않고 재귀 함수를 이용하여 매우 간결하게 구현할 수 있으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다.

[https://sunho-doing.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS-BFS](https://sunho-doing.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS-BFS)

[위상정렬](https://velog.io/@ngngs/%ED%95%9C-%EC%9E%A5%EC%9C%BC%EB%A1%9C-%EB%B3%B4%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)