[알고리즘]백트레킹

백트레킹이란

갈림길에서 길을 선택하고 길을 따라 출구를 찾지 못하면 지나온 길을 되돌아가서 다시 길을 찾는 기법

미로를 탈출 하는 방법 중에 하나

갈림길 중 한 길로 갔다가 출구를 찾지 못하면 아까 지나왔던 갈림길로 되돌아가서 '출구 아님'을 표시

깊이 우선 탐색을 하면서 가지 않아도 되는 길에 대해서는 가지치기를 통해 탐색의 효율을 올림

오름 차순으로 정렬 된 데이터를 이진트리입니다.

합이 가장 큰 값들을 찾는다면 루트 노드와 자식 노드를 각각 더해보고 작은 쪽은 가지 않아도 됩니다.

길을 찾기 위해 갈림길에서 표시를 합니다.