⭐ 깊이 우선 탐색 (DFS, Depth-First Search)
- 최대한 깊게 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 ↓ →
- 루트 노드에서 시작 - 다음 분기(Branch)로 넘어가기 전, 해당 분기를 완벽하게 탐색
- 모든 노드를 거치고자 할 때 사용하며, BFS보다 간단하며, 검색속드는 느림
- Stack / 재귀함수로 구현
⭐ 너비 우선 탐색 (BFS, Breadth-First Search)
- 최대한 넓게 이동한 다음, 더이상 갈 수 없을때 아래로 이동 → ↓
- 루트 노드에서 시작 - 인접한 노드를 먼저 탐색하며, 멀리 떨어진 정점을 제일 나중에 방문하는 순회방법
- 주로 두 노드사이의 최단 경로를 찾고 싶을때 사용
- Queue로 구현
📌 DFS / BFS의 시간복잡도
- 두 방식 모두 조건내의 모든노드를 검색한다는 점에서 시간복잡도 동일함
- 다음 노드가 방문하였는지를 확인하는 시간 + 각노드를 방문하는 시간
N은 노드, E는 간선일 때
인접 리스트 : O(N+E)
인접 행렬 : O(N²)
일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적기 때문에 인접 리스트 방식이 효율적임
📌 DFS / BFS를 활용한 문제유형
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있음
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없음.
둘 중 편한 것을 사용하자.
2) 경로의 특징을 저장해둬야 하는 문제
예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데
경로에 같은 숫자가 있으면 안 된다는 문제 등,
각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용. (BFS는 경로의 특징을 가지지 못함)
3) 최단거리 구해야 하는 문제
미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.
이밖에도
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS
📌 위상 정렬 = 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
- 진입 차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
- 진출 차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수
위상 정렬의 시간 복잡도는 O(V + E)이다.
즉, 정점의 갯수 + 간선의 갯수만큼 소요되므로 매우 빠른 알고리즘 중 하나이다
📌 큐를 이용하는 위상 정렬 알고리즘의 동작 방식
- 진입차수가 0인 모든 노드를 큐에 넣는다.
- 큐가 빌 때 까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
- 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.
'Data Architect > Data Structure' 카테고리의 다른 글
자료구조의 특징 (0) | 2023.02.05 |
---|---|
Time Complexity & Greedy & Brute Force (0) | 2022.09.27 |
Tree & Graph (2) | 2022.09.23 |
JSON_Recursive (0) | 2022.09.21 |
Recursion (0) | 2022.09.20 |