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

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

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

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

위상정렬