알고리즘 개념[실전] - 깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS)에 대해 설명하기 전 그래프 관련 간단한 용어부터 정리하겠습니다.

'그래프' 는 '노드' 와 '에지' 로 구성된 집합입니다.

• 노드 : 데이터를 표현하는 단위
• 에지 : 노드를 연결

깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나로, 보통 'DFS' 라고 합니다.

• 탐색 : 많은 양의 데이터 중에서 찾고자 하는 데이터를 찾는 과정을 의미.

• 그래프 탐색 알고리즘 : 그래프(비선형 자료구조)의 모든 꼭짓점(Node 또는 Vertex)을 방문하는 알고리즘을 말한다.

• 비선형 자료구조 : 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태.
  ex) 그래프

• 선형 자료구조 : 원소들을 하나씩 순차적으로 나열한 형태.
  ex) 리스트, 큐, 스택 등...

DFS는 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다.

가장 큰 특징으로는 다음과 같습니다.

• 재귀 함수로 구현
• 스택 자료구조 이용

시간 복잡도 : O(V + E)

• V : 노드 수
• E : 에지 수

핵심이론

DFS 구현 시 핵심적인 내용은 한 번 방문한 노드를 다시 방문하면 안된다는 것(어떤 노드를 방문했었는지에 대한 여부를 기록하고 검사해야한다)과, DFS 탐색 방식은 후입선출 특성을 가진다는 것입니다.

• 일반적으로 DFS 구현 시, 스택 성질을 갖는 재귀함수로 많이 구현한다.

1. DFS를 시작할 노드를 설정 및 자료구조 초기화
2. 스택에서 노드를 꺼낸 뒤 꺼낸 노드의 인접 노드를 다시 스택에 삽입
3. 스택 자료구조에 값이 없을 때까지 반복하기