[파이썬] 탐색 알고리즘 정리 - 백트래킹

백트래킹 (*Notion AI의 설명)

백트래킹(Backtracking)은 해결책을 구하기 위해 모든 가능성을 시도해보는 것이 아니라, 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지 여부를 검사해가며 해답을 찾아가는 알고리즘입니다.

백트래킹은 대표적으로 스도쿠, N-Queen, 암호해독 등의 문제에서 활용됩니다. 이 알고리즘은 보통 재귀적으로 구현되며, 각 단계에서는 해결책 후보군 중 하나를 선택하고, 이 선택이 문제의 조건을 만족하는지 검사합니다. 조건을 만족하지 않는다면 이전 단계로 돌아가 다른 후보군을 선택합니다. 이러한 과정을 반복하면서 최종적으로 해결책을 찾아가는 것이 백트래킹의 기본적인 원리입니다.

백트래킹은 완전탐색(Exhaustive Search)과 유사하지만, 백트래킹은 불필요한 탐색을 줄이기 위해 가능성이 없는 노드를 더 이상 탐색하지 않습니다. 이러한 방법으로 백트래킹은 대규모 문제를 효과적으로 해결할 수 있습니다.

백트래킹의 장점은 해결책을 찾을 때까지 모든 가능성을 탐색하는 것이 아니라, 해결책에 대한 후보군을 구성하여 불필요한 탐색을 줄일 수 있다는 것입니다. 따라서, 백트래킹 알고리즘은 대규모 문제를 효과적으로 해결할 수 있습니다.

하지만, 백트래킹 알고리즘은 구현하기 어렵고 코드가 복잡해질 수 있습니다. 또한, 백트래킹 알고리즘은 최악의 경우 모든 경우의 수를 다 검사해야 할 수도 있습니다.

그러나, 백트래킹 알고리즘은 많은 문제에서 최적의 해결책을 찾는 데 있어서 효과적이며, 알고리즘 공부에 꼭 필요한 기술 중 하나입니다.

백트래킹 알고리즘은 대부분 재귀 함수를 이용해 구현됩니다. 재귀 함수를 이용하면 코드를 간결하게 작성할 수 있으며, 코드의 가독성을 높일 수 있습니다. 또한, 재귀 함수를 이용해 백트래킹 알고리즘을 구현하면, 코드의 일반화가 용이해집니다. 따라서, 백트래킹 알고리즘을 구현할 때는 재귀 함수를 이용해 구현하는 것이 일반적입니다.

백트래킹 알고리즘은 대부분의 경우 시간 복잡도가 지수 시간이므로, 대규모 문제를 다룰 때는 최적의 해결책을 찾는 데 있어서 효과적이지 않을 수 있습니다. 따라서, 백트래킹 알고리즘을 사용할 때는 가능한 한 불필요한 탐색을 줄이는 방법을 찾아내야 합니다.

백트래킹 알고리즘은 최적의 해결책을 찾는 데 있어서 효과적이지만, 구현하기 어렵고 코드가 복잡해질 수 있습니다. 따라서, 백트래킹 알고리즘을 구현할 때는 코드의 일반화를 고려하여 재귀 함수를 이용하는 것이 좋습니다. 또한, 가능한 한 불필요한 탐색을 줄이는 방법을 찾아내어 시간 복잡도를 최적화하는 것이 중요합니다.

백트레킹 (Backtracking)

해를 찾는 도중 막히면 되돌아가서 다시 해를 찾는 기법

• 최적화 문제, 결정 문제에서 많이 사용
• 미로 찾기 / n-Queen 문제 / Map coloring / 부분 집합의 합 등

특징

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

백트래킹과 DFS의 차이점

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

반응형

코드의 형태

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

백트래킹을 그냥 이론만 보면 사실 무슨말인지 이해하기 어려워서, 다른 백트래킹 문제에 대한 코드를 보면서 익혀보니 이해하기 더 편했던 알고리즘. 가장 유명한 N-Queen 알고리즘에 대해 참고해보면 좋을거 같다.

https://edder773.tistory.com/74

[백준 9663] N-Queen (python)