[필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해

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

DFS 깊이 우선 탐색 방법

깊이 우선 탐색 (DFS)는 하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다.

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 주로, 재귀함수 또는 Stack로 구현할 수 있다.

 

ex) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다.

 

Stack으로 이해하는 DFS

DFS 경로 => A, B, D, G, H, C

시간 복잡도와 장단점

• 인접 행렬에서의 시간 복잡도: O(V²)
• 인접 리스트에서의 시간 복잡도: O(V+E)
• V: 정점(노드)의 개수, E: 간선의 개수
• 장점
  • 현재 경로상의 노드들만 기억하면 되므로 저장공간이 비교적 적게 든다.
  • 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 (DFS와  BFS를 둘 다 사용해도 되는 문제)
    • ex) 그래프의 모든 정점을 방문하는 문제
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

• 단점:
  • 해가 없는 경로에 깊이 빠질 가능성이 있다.
    • 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다
  • 얻어진 해가 최단 경로가 된다는 보장이 없다.
    • 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

DFS를 활용하기 적합한 문제

• 경로의 특징을 저장해둬야 하는 문제 (경로 상의 노드를 기억해야하는 문제)

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다.

• 검색 대상 그래프 큰 문제 

목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있기 때문입니다.