백트래킹

알고리즘 문제를 풀다 보면 문제 분류에 '백트래킹'과 '브루트 포스'가 같이 있는 경우를 자주 볼 수 있다. 백트래킹은 가능한 모든 방법을 탐색하는 알고리즘인데, 브루트 포스와 다른 점은 정답일 가능성이 없는 경우 그 경우를 포기하고 이전으로 돌아가 탐색을 반복한다는 점이다.

이렇게 불필요한 부분을 쳐내는 방법을 가지치기(Pruning)라고 한다. 반대로 탐색하고 있는 경로가 정답일 가능성이 있다면 유망하다(Promising)고 하며 탐색을 계속한다.

 

백트래킹을 구현할 때는 주로 dfs를 사용한다. dfs는 기본적으로 마지막 노드까지 한 방향으로 탐색하는 과정을 반복하는 알고리즘이지만, 그 작동 방식을 생각해 보면 재귀적으로 여러 경로를 탐색한다는 것을 알 수 있다. 따라서 경로 탐색 중 이 경로가 불필요하다는 판단이 서면 이전 상태로 돌아가 다음 상태를 탐색할 수 있을 것이다.

def dfs():
	# 현재 경로가 유망할 경우 계속 탐색
	if promising(x):
		dfs()

위와 같이 dfs 구현 중 조건문을 추가해 구현할 수 있다.