백트래킹(알고리즘)

백트래킹이란?

모든 경우의 수를 전부 고려하는 알고리즘.
상태공간을 트리로 나타낼 수 있을 때 적합한 방식이며 일종의 트리 탐색 알고리즘.
방식에 따라서 DFS, BFS, 최선우선탐색이 있음

모든 경우의 수를 고려해야하는 문제면 DFS가 낫다. 대표적인 예는 NQueen 문제가 있다.
하지만, 트리의 깊이가 무한대가 될 때면(미로찾기에서 루프가 발생하는 경우) BFS가 낫다.
최단거리 구하기는 BFS를 사용하는게 낫다.

• 백트래킹은 조건을 만족하지 않을 경우 다음으로 넘어가서 계속 탐색하는 기법

DFS

상태공간을 나타낸 트리에서 바닥에 도달할 떄까지 한 쪽 방향으로만 내려가는 방식
한 방향으로 들어갔다가 막다른 길에 다다르면 왔던 길을 돌아가서 다른 방향으로 간다.
재귀함수로 구현할 수 있고 스택을 써서 구현할 수도 있음

BFS

BFS는 모든 분기점을 다 검사하면서 진행하는 방식
예를 들어서 가위바위보 계단오르기 게임을 할 때 철수가 원하는 지점에 갈 수 있는 최소 승리 횟수와 가은 문제
큐를 이용해서 구현한다. 각 경우를 검사하면서 발생하는 새로운 경우를 큐에 집어넣고 검사한 원소는 큐에서 뺀다.
BFS의 장점은 DFS가 못 건드리는 문제를 풀 수 있다는 것이지만 공간 복잡도가 지수 스케일로 폭발하기 때문에 가지치기를 제대로 해야함.

최선 우선 탐색

BFS에서 조금 더 발전한 방식
큐 대신 우선 순위 큐를 써서 구현

참고

https://namu.wiki/w/백트래킹