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

- 그래프 탐색

그래프 탐색은 하나의 노드에서 시작해 모든 노드를 한번씩 방문하는 것이다.

가장 기본적인 탐색으로 DFS, BFS가 있으며 이 글에서는 DFS를 다룬다. 이외에도 다익스트라(Dijkstra), 플로이드 와샬(Floyd Washall) 등이 있지만 기본이 되는 DFS, BFS를 정확하게 알고 넘어갈 필요가 있다.

- DFS(Depth First Search)

방문한 노드는 스택에 담고, 스택의 top에 있는 노드와 연결된 노드를 탐색한다. 이 때 stack에 이미 담겨있는 노드는 탐색하지 않는다. 더 이상 방문할 노드가 없다면 backtracking 하여 탐색할 다시 탐색할 노드를 찾는다.

- 구현

DFS는 위에서 설명한 그림처럼 스택을 사용하는 방법과 재귀함수를 이용하는 방법 두 가지로 구현할 수 있다. 그래프 이론과 관련된 간단한 문제가 있어 재귀함수를 통한 구현으로 한 문제 풀어보았다.
백준 2606 DFS 문제 풀이