백트래킹(BackTracking) 알고리즘

백트래킹이란?

"퇴각 검색"이라고도 하며 한정조건을 가진 문제를 푸는 전략이다.

즉, 모든 경우의 수를 시도하여 정답을 찾는 것이 아닌, 한정 조건에서의 모든 경우의 수를 시도하기 때문에 상당한 경우의 수들이 배제된다. 따라서 다중 for문 보다 빠르고 해결되는 경우가 많다.

 

해를 찾는 도중에 막히면 더 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법이다.

---

백트래킹의 구현

• 보통 백트래킹의 구현은 BFS나 DFS와 함께 구현한다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하기 떄문에 완전 탐색 기법인 BFS/DFS가 모두 구현이 가능하다.
• But. 백트래킹의 특성에서 한정 조건에 부합하지 않으면 이전 수행으로 돌아와야하기 때문에 DFS에서의 구현이 더 편하다.
• 주로 문제풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어서 답이 절대로 될 수 없는 상황을 정의하고, 그런 상황일 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 다른 경우를 탐색하도록 구현할 수 있다.

---

백트래킹 예시

 

1. 3x3 행렬 선택 게임

- 아래와 같은 행렬이 존재할 때 3개의 숫자를 선택하는 게임. 단, 선택한 숫자들의 행과 열은 모두 중복하면 안된다. 

- 가장 적은 점수를 얻는 것이 승리하는 것이라 할때 선택해야하는 숫자 3가지를 구하라

 

 

풀이방식

• 가장 쉬운 방법은 모든 방법을 다 해보는 것. 하지만 조건이 있다. 고른 숫자는 모두 행과열이 달라야 하는 것.
• 이것이 한정 조건이다. "행과열이 달라야 한다".

일반 탐색

한정조건 추가

• 이와 같이 한정 조건을 적용한 뒤에 DFS를 통해 전체 탐색을 진행하는 것이 백트래킹이다.

import sys

li = [[1,5,3],[2,5,7],[5,3,5]]
chk = [False]*3
m = sys.maxsize

def backtracking(row, score):
	if row == 4: # 재귀함수를 마치는 조건
		if score < m:
			return
	for i in range(1,4):
		if chk[i] == false: # 백트래킹에서의 한정조건
			chk[i] = true
			backtracking(row+1, score + li[row][i])
			chk[i] = false
	return 

backtracking(1,0)
print(m)

.

 

 

 

 

 

 

 

참고 문헌

https://80000coding.oopy.io/85650ea5-e541-4b12-9b86-a958a99b7533

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Back-tracking

https://veggie-garden.tistory.com/24