[개념정리(2)] 백트래킹

이번에 살펴볼 개념은 백트래킹에 관한 내용입니다.

백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다.

 

Backtracking(백트래킹)

• 완전탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략
• 대표적 예 : 재귀 호출 or 스택을 통한 DFS

백트래킹의 원리

1. 어떤 노드의 유망성을 점검 후,
2. 유망하지 않으면 배제시킨다. = 가지치기
3. 해당 노드의 부모노드로 되돌아간 후 다른 자손노드를 검색한다. → 풀이시간 단축

유망성과 가지치기

• 유망성(Promising) : 가망이 있는가 없는가를 따지는 기준
• 가지치기(Pruning) : 유망성을 따져보고, 유망하지 않는 경우의 수는 배제하는 것으로 간단히 말하면 '불필요한 부분을 쳐낸다'로 보면 된다.

 

 

 

<참고>

https://velog.io/@leobit/DFS-BFS-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking

DFS, BFS, 백트래킹(Backtracking)