백트래킹(Back Tracking)
; 모든 경우의 수를 전부 고려하는 알고리즘
- 상태공간을 트리로 나타낼 수 있을 때 적합(트리 탐색 알고리즘)
▶ DFS(Depth-First Search) ; 깊이 우선 탐색
; 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
- 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색
- 스택(stack) 혹은 재귀함수를 통해 구현
- 모든 경로를 방문해야 할 경우 사용에 적합
▶ BFS(Breadth-First Search) ; 너비 우선 탐색
; 최대한 넓게(근접한 것부터) 이동한 후, 더 이상 갈 수 없을 때 아래로 이동
- 루트 노드 혹은 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
- 큐 사용
- 최소비용(모든 것을 탐색하는 것보다, 최소 비용이 우선일 때)에 적합
'알고리즘' 카테고리의 다른 글
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
|---|---|
| [알고리즘] 배열과 연결리스트 (0) | 2022.05.21 |
| [알고리즘] 정렬(삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬) (0) | 2022.05.16 |
| [알고리즘] 자료구조란 ? (0) | 2022.05.15 |
| [알고리즘] 알고리즘이란 ? / 알고리즘의 종류 (0) | 2022.05.14 |
| [알고리즘] 그리디 알고리즘 (0) | 2022.04.19 |
| [알고리즘] 트리(Tree) (0) | 2022.04.17 |
| [알고리즘] 이진 탐색 알고리즘 (0) | 2022.04.15 |
