백트래킹

백트래킹이란 경로를 따라 경우의 수를 탐색하되, 탐색 도중 해당 경로가 앞으로도 조건을 충족할 수 없다고 판단되면 그 경로를 즉시 가지치기를 하고 이전 상태로 되돌아가는 알고리즘입니다.

백트래킹으로 문제를 해결할 때 4가지 요소를 고려해야합니다.

• 기저조건
• 가지치기
• 내려가기
• 되돌아가기

기저조건이란 하나의 경우의 수가 완성되었는지를 판단하는 조건으로, 답을 출력하거나 기록하는 시점이 됩니다.

가지치기란 현재 경로가 앞으로도 조건을 충족할 가능성이 있는지를 검사하는 지점이며, 가능성이 없다고 판단되몀ㄴ 해당 경로의 탐색은 즉시 중단됩니다.

내려가기는 경로를 확장하기 위해 상태를 하나 더 선택하는 과정이며, 되돌아가기는 탐색이 끝난 후 상태를 원래대로 복구하는 과정입니다.

백트래킹를 적용하기 위해서는 문제에서 위의 4 요소를 뽑아낼 수 있어야합니다.