TIL 34 백 트래킹

hyeongirlife·2021년 11월 16일
0

TIL

목록 보기
35/90

백 트래킹

해를 찾는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다.

학창시절 수형도라고 부르는 나뭇가지를 그려 모든 경우의 수를 생각했던 것에서 더 나아가, 절대로 안될 것 같은 부분은 제외하고 경우의 수를 생각하는 알고리즘이다.

주로 문제 풀이에서는 DFS 등 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어 답이 절대로 될 수 없는 상황을 정의한다. 그러한 상황일 경우 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색한다.

ex) 백준 9633번 - N-Queen

profile
머릿속에 있는 내용을 정리하기

0개의 댓글