4-1 탐색(DFS)

 깊이 우선 탐색(depth first search)은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

 

깊이 우선 탐색의 특징으로 보통 재귀 함수나 자료구조중에 스택을 이용하여 구현하는데 DFS는 선출후입의 구조를 가지고 있기 때문이다.

 

시간복잡도는 O(V + E)로 V는 노드의 개수이고, E는 엣지의 개수이다.

 

재귀 함수를 이용하여 구현하면 스택오버플로우를 유의하며 구현하여야 한다.

 

깊이 우선 탐색의 핵심 이론

 

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 추가적인 배열이 필요하다.

 

이미지 출처:https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

 

 

https://mngprog.tistory.com/34

11724번 (silver 2)

위의 백준 문제를 DFS를 이용하여 해결하면 이해하기 쉽다.