📘[Search] 백트래킹에 대해서…

백트래킹이란?

백트래킹(Back Tracking)이란, 해결책을 구하기 위해 모든 가능성을 시도해보는 것이 아니라, 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지 여부를 검사해가며 해답을 찾아가는 알고리즘이다. (Notion AI 설명)
대표적인 문제로 ‘스도쿠’, ‘N-Queen’, ‘암호해독’ 등이 있다.

즉, 백트래킹은 해를 찾는 도중 막히면 되돌아가서 다시 해를 찾는 방식이다.

• 최적화 문제 혹은 결정 문제에서 많이 사용한다.

백트래킹을 사용하는 경우?

for문으로는 확인이 불가능한 경우에 적용하면 된다.
무슨 말이냐? 깊이가 달라질 때 사용하면 된다. (유튜브 - 개발자 장고)

백트래킹의 특징

• 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 판단되면 그 노드의 부모로 되돌아가 그 다음 자식 노드를 탐색한다.
  • 유망성: 해답의 가능성이 있는 경우를 유망하다고 함.
• 어떤 노드를 방문했을 때, 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다.
• 가지치기 사용 가능핟. (유망하지 않은 노드가 포함되는 경로는 고려하지 않는 기법임)
• 기본적으로 재귀의 성격을 띄는 형태.

백트래킹과 DFS의 차이점

백트래킹

• 어떤 노드엣 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음 -> 횟수 감소
• 불필요한 경로의 조기 차단
• N! 가지의 경우의 수를 가진 문제에 대해 백트래킹을 시도하면 일반적으로 경우의 수가 줄어들지만, 최악의 경우에는 처리가 불가능해짐
• 모든 후보를 검사하지 않음

DFS

• 모든 경로를 추적함
• N! 가지의 경우의 수를 가진 문제에 대해 DFS를 이용하면 처리가 불가능함
• 모든 후보를 검사함

수도 코드

def 재귀함수(n):
	if 정답이면 :
		출력 or 저장
	else : 정답이 아니면 :
		for 모든 자식 노드에 대해서:
			if 정답에 유망하다면(답의 가능성이 있으면) :
				자식노드로이동
				재귀함수(n+1)
				부모노드로 이동

백트래킹의 경우, 유망 조건을 따로 함수로 만들어서, 아래와 같이 구성하는 경우가 많다고 한다.

def 백트래킹(n):
	if 정답이면 :
		출력 or 저장
	else :
		for 모든 자식 노드에 대해 :
			if 유망한지확인(m) :
				자식노드로 이동
				백트래킹(n+1)
				부모노드로 이동

def 유망한지확인(m):
	if 조건에 안맞으면 :
		return False
	return True
출처: https://edder773.tistory.com/75 [개발하는 차리의 공부 일기:티스토리]

참고자료

[파이썬] 탐색 알고리즘 정리 - 백트래킹
코딩테스트 알고리즘 - 3. 백트래킹