깊이 우선 탐색

개념

깊이 우선 탐색은 DFS라고도 하며, 한 방향으로 가능한 깊게 내려가며 탐색하는 방법이다. 더 이상 갈 곳이 없으면 이전 상태로 돌아와 다른 경로를 탐색한다.

동작 방식

DFS는 보통 OPEN과 CLOSED에서 OPEN을 스택처럼 사용한다. 나중에 들어온 노드가 먼저 탐색된다.

장점

• 메모리 사용량이 비교적 적다.
• 깊은 곳에 해가 있으면 빨리 찾을 수 있다.
• 구현이 단순하다.

단점

무한히 깊은 경로에 빠지면 해를 찾지 못할 수 있고, 최단 경로를 보장하지 않는다. 중복 상태를 관리하지 않으면 무한 반복이 발생할 수 있다.

분기 수를 $b$, 최대 깊이를 $m$이라 하면 트리 탐색 기준 복잡도는 보통 다음과 같다.

$$\text{시간}=O(b^m),\text{공간}=O(bm)$$