깊이 우선 탐색 알고리즘이란?

오늘은 그래프 탐색 알고리즘 중 하나인 깊이 우선 탐색에 대해 알아보려고 한다

먼저 깊이 우선 탐색은 이름에서 알 수 있듯이 시작 정점에서 가장 깊숙이 들어간 뒤 더 이상 방문할 수 있는 곳이 없으면 이전 정점으로 돌아와 다른 정점으로 깊이 탐색을 진행하는 방식의 알고리즘이기 때문에 깊이 우선 탐색이라고 붙여졌다

깊이 우선 탐색이란?

깊이 우선 탐색(DFS, Depth First Search)은 그래프의 모든 정점을 방문하는 방식 중 하나로 그래프에서 한 노드의 자식을 향해 탐색을 진행하며 더 이상 방문할 노드가 없을 때 이전 노드로 돌아와 탐색을 계속하는 방식으로

일반적으로 스택 자료구조나 재귀 호출을 사용하여 구현하며 그래프의 모든 정점을 방문하게 된다

깊이 우선 탐색의 작동 방식

이러한 깊이 우선 탐색은 다음과 같은 방식으로 작동한다

1. 시작 노드를 스택에 넣고 방문 처리를 한다
2. 스택의 최상단 노드에서 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다
3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
4. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

글로만 보면 잘 이해가 안될 수 있으니 예시를 들어 설명하자 그래프에서 A라는 정점에서 시작하여 깊이 우선 탐색을 진행한다고 했을 때

그래프:

    A
   / \
  B   C
 /     \
D       E
         \
          F

진행 순서:

A -> B -> D -> C -> E -> F

와 같은 순서로 노드를 방문하게 된다

깊이 우선 탐색의 장단점

마지막으로 깊이 우선 탐색 알고리즘의 장단점을 알아보자

장점:

1. 현재 경로상의 노드들만을 기억하면 되므로 저장 공간의 요구량이 적다
2. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다

단점:

1. 해가 없는 경로에 깊이 빠질 가능성이 있다
2. 모든 경로를 탐색하는 경우 시간이 오래 걸릴 수 있다