[알고리즘] DFS(깊이 우선 탐색)

DFS(Depth-First Search)란?

DFS란 그래프 탐색 기법 중 하나이다. 말 그대로 시작 노드에서 부터 한 쪽으로 탐색을 시작하면 그 방향에 있는 모든 노드들을 방문하고 다른 방향의 노드들을 탐색하는 기법이다.

 

DFS의 특징 및 사용법

DFS 특징

• DFS는 보통 재귀함수로 구현되며 탐색하고자 하는 그래프의 규모에 따라서 시간 복잡도가 달라지게 됩니다. DFS의 시간 복잡도는 O(V+E)(V=노드 수, E=간선 수)로 표현 됩니다. 
• DFS는 한번 방문한 노드들을 다시 방문해서는 안되므로 노드 방문 여부를 체크할 수 있는 배열이나 리스트를 가지고 있습니다.
• 다른 그래프 탐색 기법인 BFS에 비해 구현이 단순하다는 장점이 있지만 그만큼 검색 속도에 있어서는 뒤쳐집니다.

DFS 사용법 및 사용문제

•  DFS는 보통 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등 문제에서 활용 될 수 있습니다.
• 모든 노드들을 방문해야할때 사용하는 경우가 많습니다.
• 그래프를 만들때 보통 인접 리스트로 하지만 인접 행렬을 이용하여 구현도 가능합니다. 다만 인접 리스트가 더 효율적이기 때문에 보통은 인접 리스트로 구현하는 편이 많습니다. 대신 노드와 간선의 수가 적은 경우 인접 행렬의 구현 난이도가 더 낮기 때문에 사용하는 정도 입니다.

 

DFS 구현 과정

1.  시작 노드를 결정하고 사용할 자료구조들 초기화
   
   • 먼저 주어진 문제에 있는 그래프를 인접 리스트든 2차원 배열로 표현을 하든 그래프로 만든다.
   • 방문 여부를 저장하기 위한 배열 or 리스트도 시작 노드를 제외한 나머지를 Fasle로 표현하며 초기화한다.
   • 방문해야 할 노드를 저장하는 스택에 시작노드를 넣은 채로 초기화 한다.
2. 스택에서 노드를 꺼내고 해당 노드의 인접 노드를 스택에 넣기
   • 스택에서 현재 있는 노드를 꺼낸 후 그래프를 이용하여 해당 노드의 인접 노드를 알아내고 스택에 넣는다.
   • 스택에 들어간 노드들은 모두 방문을 한 것으로 간주하고 배열을 고친다.
   • 스택을 pop하여 해당 노드의 인접 노드를 다시 알아내고 그 노드를 다시 스택에 넣는다.
   • 해당 과정을 반복한다.
3. 모든 노드를 방문하고 스택에 노드가 없을 때까지 반복
   
   • 2번 과정을 반복하면서 방문을 한 노드를 제외하고 방문하지 않은 노드들만 스택에 넣고 빼면서 모든 노드들을 탐색한다.
   • 여기서 스택을 빠져나온 순서가 방문한 순서가 된다.