깊이 우선 탐색 (DFS : depth first search)는 너비 우선 탐색과 동일하게 어떠한 자료구조를 대상으로 특정한 값을 찾거나, 전체를 탐색하기 위한 알고리즘 중 하나이다.
DFS를 이용한 미로찾기 예시
이때, BFS와는 다르게 탐색 우선순위가 중요하다. (BFS라 하여 탐색 우선순위가 전혀 존재하지 않는 것은 아니지만, 그 우선순위가 전체 시행에 큰 영향을 주지 않는다.)
위의 이미지를 보면, 현재 위치 (파란색)에서 이동 가능한 방향들 중 탐색 우선순위상(오른쪽 화살표들) 가장 우선순위가 높은 방향으로 이동하는 모습을 볼 수 있다. 만약 진행 도중 더 이상 진행할 수 없을 경우 가장 가까운 다른 이동 가능 지점으로 후진하여 탐색을 계속 진행해 나간다.
이미지에서는 뒤쪽으로 돌아가는 모습을 직접 나타냈지만, 일반적으로 분기점을 스택에 넣거나, 재귀 함수로 구현하여 빠르게 가까운 이동 가능 지점으로 돌아간다.
DFS는 여러 개의 탐색 가능한 지점이 존재할 때, '현재' 위치를 기준으로 '우선순위가 가장 높은' 지점으로 탐색을 진행한다.
예를 들어 아래와 같은 그래프가 있다고 가정하자, 1번 노드부터 DFS를 하려 한다.
이동지점을 선택할 우선순위는 각 노드의 값이라고 하자. (= 더 큰 노드로 이동)
1번 노드에서 시작할 것 이기 때문에 "현재" 노드 (=파랑 노드)는 1번이다. 현재 노드에서 이동 가능한 지점은 2곳으로, 2번 노드와 3번 노드이다.
이중 이동 규칙인 "이동 가능한 노드 중 가장 큰 노드"는 3번 노드가 된다.
그러므로 1번 노드는 이미 탐색한 노드 (=빨강 노드)가 되고, 3번 노드가 현재 노드가 된다.
3번 노드에서는 연결이 3방향 (1번, 2번, 5번)이지만. 이중 1번 노드는 이미 탐색되어 있으므로 이동 가능한 노드에서 제외한다. 5번 노드가 이동 가능한 노드 중 가장 큰 노드가 되므로 다음 이동은 5번으로 하게 된다.
같은 규칙을 적용하면 다음 이동할 지점은 6번임을 알 수 있다.
만약 6번 노드를 찾는 행위를 하고자 한다면, 이대로 종료해도 문제없다. 하지만 그래프 전체를 탐색하고자 한다면 문제가 발생하는데, 6번 노드에서 이동 가능한 지점이 없다는 것이다.
이때는 1 -> 3 -> 5 -> 6 순서로 탐색을 했기 때문에 바로 전 단계인 5번 노드로 "현재" 노드를 옮겨야 한다.
이때 스택 등 FILO 자료구조를 이용하면 된다.
스택을 같이 이용하는 장면은 아래의 GIF를 참고하자.
여튼 5번 노드에서 4번 노드로 이동이 가능하며
4번 노드에서 2번 노드로 이동이 가능하다.
최종적인 탐색 순서는 1 -> 3 -> 5 -> 6 -> 4 -> 2 순 탐색이 된다.
만약 위의 예시에서 2번 노드까지의 최단거리를 구하고 싶었다고 가정해보자. 이때 DFS를 사용했다면 6번째로 2번 노드에 도착하게 된다. 즉 최단거리를 구하는 문제에서 DFS를 이용하기는 BFS를 이용하는 것에 비해 일반적으로 어렵다.
(불가능하지 않다, 다만 구현과 시간 복잡도에서 대부분 불리하다.)
하지만 방문 순서가 스택 등에 같이 저장된다는 특성과, 탐색 방향 (= 탐색 우선순위)를 결정할 수 있다는 점은 BFS에 없는 장점이다. 예를 들어 이진트리를 이용한 binary search tree를 이용할 때엔 DFS를 쓰게 된다.
이전 BFS 포스팅 때에도 언급했지만 각각의 특징을 이해한 뒤, 응용한다면 한정적인 자료구조, 한정적인 목적으로 암기하여 사용하는 초급 알고리즘 단계를 빠르게 탈출할 수 있을 것이다.
