[알고리즘] DFS 깊이 우선 탐색

 

깊이 우선 탐색 Depth-First Search

그래프의 모든 노트를 탐색하는 그래프 완전 탐색 기법 중 하나

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

재귀함수 구현, 스택 자료 구조 이용하는 특징을 가지고 있다

O(노드 수 + 엣지 수)의 시간 복잡도를 가진다

유의할 점은 실제 구현 시 재귀함수를 이용하므로 스택 오버플로에 유의해야 한다

 

DFS 동작

한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요함

그래프는 인접 행렬이나 인접 리스트로 표현, 대부분 인접 리스트로 표현

 

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

DFS를 위해 필요한 초기 작업

1. 인접 리스트로 그래프 표현하기
2. 방문 배열 초기화하기
3. 시작 노드 스택에 삽입하기

 

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기

pop을 수행하여 노드를 꺼내고 꺼낸 노드를 탐색 순서에 기입

인접 리스트의 인접 노드를 스택에 삽입하여 방문 배열을 체크

 

3. 스택 자료구조에 값이 없을 때까지 반복

앞선 과정을 스택 자료구조에 값이 없을 때까지 반복, 이미 다녀간 노드를 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심

 

탐색 순서는 1 → 3 → 4→ 6 → 2 → 5

탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색하고 다른 쪽 분기로 이동하여 탐색

 

관련 문제 보기

백준 11724번 연결 요소의 개수