알고리즘 개요 및 소개
백 트래킹(BackTracking) 또는 퇴각 검색(Backtrack)으로 불리는 이 방식은 DFS(깊이 우선 탐색) 구조를 기반으로 문제를 푸는 전략이다.
백 트래킹은 탐색을 진행하다가 더 갈 수가 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 이런 이름이 붙었다.
백트래킹은 주로 재귀적으로 구현하며 백트래킹 알고리즘마다 DFS에서 조금씩의 변형이 일어나지만 기본적으로는
모두 DFS의 범주에 속한다. 백 트래킹은 실제 구현 시 고려할 수 있는 모든 경우의 수를 *상태 공간 트리(State Space Tree)를 통해 표현한다. 상태 공간 트리를 탐색하면서 조건이 맞지 않으면 다른 곳으로 넘어가서 탐색을 진행하며 아래와 같은 기법이 존재한다.
- Promising: 해당 루트가 조건에 맞는지 검사하는 기법
- Pruning(가지치기): 조건에 맞지 않으면 포기하고 다른 루트로 돌아가서, 탐색의 시간을 절약하는 기법
상태공간 트리(State Space Tree): 문제 해결의 중간과정(상태)을 각각의 노드로 나타낸 트리
관련 글
[자료구조 알고리즘/탐색 알고리즘] - 깊이 우선 탐색(Depth First Search)
[온라인 코딩/탐색(Search)] - [백준] 15649번 N과 M
후기
3월의 마지막 글인 백 트래킹에 대해서 알아보았다. 사실 백트래킹 자체는 DFS와 비슷하기 때문에 정리할 내용이 많이 없었다.
핵심은 상태공간 트리라고 생각하는데 여러 문제를 풀어보면서 배워볼 예정이다.
출처 및 레퍼런스
Wiki: https://ko.wikipedia.org/wiki/퇴각검색
Book: 쉽게 배우는 알고리즘 문병로 저
'자료구조 알고리즘 > 탐색 알고리즘(Search)' 카테고리의 다른 글
| [알고리즘] A* 치즈 찾기-맵 툴 (0) | 2020.08.29 |
|---|---|
| [알고리즘] A* 알고리즘 (0) | 2020.08.24 |
| [알고리즘] 다익스트라 알고리즘(Dijkstra algorithm) (0) | 2020.02.25 |
| [알고리즘] 합집합 찾기(Union-Find) (0) | 2020.02.14 |
| [알고리즘] 최소 비용 신장 트리(Minimum Cost Spanning Tree) (0) | 2020.02.11 |
