[7] 백트래킹 알고리즘 (파이썬 구현)

[1] 백트래킹이란

한정 조건을 가진 문제를 푸는 전략 모든 경우의 수를 시도하여 문제의 정답을 찾아감

• 한정 조건에서의 모든 경우의 수를 시도 ⇒ 상당한 경우의 수들이 배제되므로 다중 for문보다 빠름

(1) 원리

1. 각 단계에서 해결책 후보군 중 하나를 선택하고 이 선택이 조건을 만족하는지 검사
2. 조건을 만족하지 않으면 이전 단계로 돌아가 다른 후보군 선택
3. 1,2 과정을 반복하면서 최종적으로 해결책을 찾아가는 것이 백트래킹의 기본적인 원리

(2) 구현

한정 조건을 걸어 완전탐색에서 유망하지 않은 시도를 걸러내는 것

• DFS, BFS를 사용하여 구현
• 모든 경우에서 한정 조건을 만족하는 경우를 탐색
• 한정 조건에 부합하지 않다면 이전 수행으로 돌아와야하므로 DFS의 구현이 편함

코드의 형태

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

 

 

[2] 백트래킹으로 순열, 조합 구현하기

(1) 순열

1. 간단하게 재귀함수를 통해 매개변수에 하나씩 원소를 더해줌
2. 길이가 우리가 원하는 만큼 달성됐다면 arr를 리턴

• visited라는 방문 체크 배열이 필요

array = [1,2,3]
k = 2  # 선택할 숫자의 개수
visited = [False for i in range(len(array))]

def backtracking_perm(arr):
	if len(arr) == k:
		print(arr, end=" ")
		return arr
	
	for i in range(len(array)):
		if visited[i] == False:
			visited[i] = True
			backtracking_perm(arr + [array[i]])
			visited[i] = False

backtracking_perm([])
# [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2]

 

(2) 중복 순열

• visited 배열 없애기

array = [1,2,3]
k = 2  # 선택할 숫자의 개수

def backtracking_perm2(arr):
	if len(arr) == k:
		print(arr, end=" ")
		return arr
	
	for i in range(len(array)):
		backtracking_perm2(arr + [array[i]])

backtracking_perm2([])
# [1, 1] [1, 2] [1, 3] [2, 1] [2, 2] [2, 3] [3, 1] [3, 2] [3, 3]

 

(3) 조합

1. 순서를 고려하지 않으므로 중복을 제거해줘야함
2. 순열에서 중복만 피해주면 됨 → idx 매개변수 추가
3. 앞의 것 무시, 그 다음 것부터 배열을 만듦

array = [1,2,3]
k = 2

def backtracking_comb(idx, arr):
	if len(arr) == k:
		print(arr, end=" ")
		return arr
	
	for i in range(idx, len(array)):
		backtracking_comb(i+1, arr + [array[i]])

backtracking_comb(0, [])
# [1, 2] [1, 3] [2, 3]

 

(4) 중복 조합

• backtracking_comb함수에 i+1 대신 i

array = [1,2,3]
k = 2

def backtracking_comb2(idx, arr):
	if len(arr) == k:
		print(arr, end=" ")
		return arr

	for i in range(idx, len(array)):
		backtracking_comb2(i, arr + [array[i]])

backtracking_comb2(0, [])
# [1, 1] [1, 2] [1, 3] [2, 2] [2, 3] [3, 3]

 

 

---

참고자료 및 출처

https://edder773.tistory.com/75 

https://jungsiroo.github.io/algorithm/2023-04-05-backtrack/