요약
깊은 우선탐색(DFS)는 그래프를 재귀함수를 이용하여 말단 노드부터 탐색하는 완전탐색 알고리즘
깊은 우선 탐색, DFS
완전 탐색 기법중 하나인 깊은 우선 탐색 (DFS, Depth-First Search) 알고리즘은 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
💡완전 탐색
그래프에 있는 모든 노드를 탐색한다는 의미다.
너비 우선 탐색(BFS), 깊이 우선 탐색(DFS), 브루트 포스(Brute Force), 백트랙킹(BackTracking), 비트 마스크(Bit Mask), 순열(Permutation), 재귀함수(Recursion Function) 이 완전 탐색의 알고리즘이다.
특징
- 그래프 탐색 시 어떤 노드를 방문했는지 노드 방문 여부나 조건을 반드시 확인해야 한다.
-> 확인 하지 않을 경우 무한 루프에 빠져 스택 오버 플로우를 발생하게 된다.
💡오버플로우(overflow)
호출한 함수가 실행될때 스택에 쌓이게 되는데 루프나 재귀함수로 인해 무한대로 돌게 되면 스택에 쌓이는 함수가 계속 쌓이게 된다. 일정 수준 이상으로 쌓이게 될 경우 운영체제는 오버플로우를 발생시키며 해당 프로그램을 종료시킨다.
-
깊이 우선 탐색은 순환알고리즘(재귀함수)로 구현
-
스택 자료 구조를 이용
장단점
시간 복잡도
| 리스트 | 시간 복잡도 |
|---|---|
| 인접 리스트 | O(N + E) |
| 인접 행렬 | O(N) |
💡 인접행렬을 사용하는 경우도 있지만 대부분 인접 리스트를 사용한다!
장점
- 깊이 우선탐색(DFS)와 너비우선탐색(BFS)를 사용하는 경우 깊이 우선 탐색(DFS) 구현이 간단하다.
-> 모든 노드를 방문하는 경우 - 노드 해의 깊이가 깊은 경우 해를 빨리 구할 수 있다.
단점
- 해가 없는 경우 한 경로에 깊이 빠질 수 있다.
-> 구한 해의 경로가 최단 경로가 된다는 의미를 뜻하지는 않는다.
- 구한 해의 경로가 최단 경로라고 할 수 없다.
-> 깊이 우선 탐색은 단순히 말단 노드부터 조사해 해와 일치하면 끝내버리므로 이는 최적의 경로라고는 할 수 없다.
핵심 이론
깊이 우선 탐색(DFS)은 한 번 방문한 노드를 다시 방문 하면 안되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접리스트로 표현한다. 그리고 DFS의 탐색 방식은 후입 선출 특성을 가지므로 스택을 사용하여 설명한다.
💡스택 VS 재귀함수
설명의 편의를 위해 스택을 사용했지만 DFS 구현은 스택보다 스택의 성질를 갖는 재귀 함수로 많이 구현을 한다.그냥 깊이 우선 탐색(DFS)은 재귀함수 만들고 호출하면 된다.
- 깊이 우선 탐색(DFS)를 시작할 노드를 정한 후 사용할 자료구조(인접리스트) 초기화 하기
DFS를 위해 필요한 초기 작업은 인접리스트로 그래프 표현하기, 방문 배열 초기화하기, 시작 노드 스택에 삽입하기이다.
💡방문배열
방문 배열은int형이나boolean형을 사용하는데 이건 취향이다
- 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
이제pop을 수행하여 노드를 꺼낸다. 꺼낸 노드를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하며 방문 배열을 체크한다.
💡2 vs 3
스택에 2와 3 중 먼저 넣는 순서는 상관없다!
- 스택 자료구조에 값이 없을 때까지 반복
스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조하여 살펴보자
- 스택이 다 비게 되면 깊이 우선 탐색(DFS)는 종료된다.
적용할 만한 문제
풀려고 하는 문제가 가장 말단의 노드에서 값을 얻어와 계산하는 방식이라면 깊은 우선 탐색(DFS)를 이용해 말단 노드의 값부터 가져와 이전에 호출했던 함수에 값을 넘겨주면 된다.
그 외
- 단절점 찾기
- 단절선 찾기
- 사이클 찾기
- 위상 정렬
- 경로의 특징을 기억(방문 노드를 저장)하는 문제
- 검색 대상의 그래프가 큰 문제
-> 목표 노드가 깊은 단계에 있을 경우 DFS를 이용해해를 빨리 구할 수 있다.
