백트래킹

백트래킹(Back-Tracking)?

트리 탐색 알고리즘의 일종이다. 거슬러 추적한다는 의미를 담고 있다. 이전 노드로 돌아가서 다시 다른 노드들을 탐색한다는 것.

깊이 우선 탐색 [Depth First Search] , 너비 우선 탐색 [Breadth First Search] , 최선 우선 탐색 [Best First Search] 로 나뉜다.

DFS의 특징

-깊이를 고려하는 문제인지 확인해야한다. 무한한 깊이일 경우 피해야 한다.

-스택 오버플로를 조심해야 한다. 재귀 호출을 이용할 시, 너무 많이 시도할 경우 스택 오버 플로가 발생한다.

-스택을 이용한 방법 / 재귀 호출을 이용한 방법으로 두가지로 구현이 가능하다.

BFS의 특징

-최단 거리 구하기 문제에서 사용하기 알맞다. 레벨별로 서치하기 때문이다.

-큐를 이용한 방식으로 구현이 가능하다.

Best Fs의 특징

-데이터의 중요도를 고려한 탐색 알고리즘이다.

-우선 순위 큐를 이용한다.