백트래킹 알고리즘

백트래킹이란?

해를 찾기 위해 가능한 한 모든 경우를 시도하되, 불필요한 경우라고 판단했을 때는 조기에 포기하여 탐색 시간을 줄이는 방식이다.

"부분 후보 해" 라는 개념과 그 해가 유효한 해로 완성될 수 있는지에 대한 검증이 가능한 문제에만 적용될 수 있다('상태공간을 트리로 나타낼 수 있을때만'이라고 봐도 무방하다). 한번의 검증으로 많은 후보를 제거할 수 있기 때문이다. 

 

* 단, 트리의 깊이가 무한대가 되는 문제에서는 사용하면 안된다.

 

예시 : 수도쿠 퍼즐

출처 : https://en.wikipedia.org/wiki/Backtracking

 

상태공간을 트리로 나타낸다면 거대한 트리가 존재하고 각 칸마다 하나의 레벨, 각 칸에 1~9 중 어느 숫자를 넣는지 노드를 따라가며 탐색하는 상황이다.

 

백트래킹 방법

1. 해를 구성하는 모든 후보들에 대해
2. 현재 선택이 유망한지 검사 (Promising 여부 판단)
3. 유망하다면 재귀적으로 다음 단계로 진행
4. 그렇지 않다면 백트래킹 (이전 단계로 돌아감+해당 노드 제거)

 

4번을 통해 불필요한 탐색 경로를 조기에 제거하여, 시간 복잡도를 낮출 수 있다.

백트래킹 알고리즘 문제풀이들

https://chabin37.tistory.com/107

[JAVA] 백준 9663 N-Queen

https://chabin37.tistory.com/108

[JAVA] 백준 12100 2048(Easy)

https://chabin37.tistory.com/145

[JAVA] 백준 1987 알파벳

.https://chabin37.tistory.com/152

[JAVA] 백준 1799 체스