백트래킹(Backtracking) 알고리즘

백트래킹 알고리즘이란?

백트래킹 알고리즘은 모든 가능한 경로를 탐색하는 데 사용되는 알고리즘입니다. 다만, 이때 모든 가능성을 탐색한다는 것은 그 경로가 해결책으로 이어질 가능성이 있을 때만 해당 경로를 따라가는 것을 의미합니다. 만약 그 경로가 해결책ㅇ로 이어질 가능성이 없다면 그 즉시 해당 경로는 버림(pruning)되며 다른 경로를 탐색합니다.

 

백트래킹은 주로 결정 문제에서 사용되며, 이러한 문제는 해결책이 존재하는가? 또는 모든 해결책을 찾을 수 있는가?와 같은 질문에 대답하는 데 사용됩니다.

 

백트래킹 알고리즘의 작동 방식

백트래킹 알고리즘은 깊이 우선 탐색(DFS)와 비슷한 방식으로 작동합니다. DFS와 마찬가지로 백트래킹도 트리 또는 그래프의 모든 경로를 탐색하지만, 백트래킹은 어떤 경로가 해결책으로 이어질 수 없음을 판다하면 즉시 해당 경로를 포기하고 다른 경로를 탐색합니다.