[Algorithm] 백트래킹(backTracking)이란?

최근에 알고리즘 문제를 풀다가 백트래킹이라는 개념을 사용해야 하는 문제를 접하게 되었는데,

어떤 개념인지 잘 짚고 넘어가면 좋을 것 같아서 정리해 보려고 합니다!

 

백트래킹이란?

제약 조건 만족 문제에서 해를 찾기 위한 전략입니다.

보통 DFS랑 같이 사용되곤 하는데요.

문제에서 요구하는 해를 찾기 위해 제약 조건에 따라 점진적으로 방문하다가, 해당 노드가 제약 조건에 만족할 수 없다고 판단하였을 때, 즉시 이 노드는 더이상 방문할 필요가 없음을 판단하고, 뒤로 돌아가 다른 노드를 탐색하며, 최적의 해를 찾는 방법이라고 설명할 수 있습니다.

 

조건에 맞지 않을 경우 더이상의 탐색을 포기하는 것을 가지치기라고 얘기하며, 주어진 해를 찾는 탐색의 시간을 절약하는 기법입니다.

 

결론적으로 백트래킹은 DFS로 트리 구조를 깊이우선탐색으로 진행하다가, 조건에 부합하지 않은 노드일 경우, 가지치기를 해서 더이상 깊이우선탐색을 진행하지 않는다고 생각하면 되겠네요!

 

그림으로 정리해 보겠습니다.

 

이러한 트리가 있다고 가정하고,

1은 제약 조건에 부합하고, 2도 제약 조건에 부합한 상태인데, 4와 5는 제약 조건에 부합하지 않은 상황이라고 가정해 보겠습니다.

 

그러면 그 아래에 있는 6과 7 또한, 방문할 필요가 없기 때문에, 가지치기를 해 버리게 되는 것이죠.

더불어 4와 5가 제약조건에 부합하지 않기 때문에 2 역시 방문할 필요가 없기 때문에 이전 노드로 다시 거슬러 올라가게 됩니다.

그리고 다음 노드(3)을 다시 깊이우선탐색을 하게 되는 것입니다!

 

항상 뭔가 이론을 공부하면 알 것 같은데, 막상 구현하려고 하면 막막한 것 같은 ㅠㅠ...

많은 문제를 풀어보도록 합시당