코딩테스트 - 백트래킹(BackTracking)

백트래킹(BackTracking)은 문제를 해결하기 위해 모든 해결책(모든 가능성)을 시도하는 것이 아니라, 해결책에 대한 후보군을 구성해서 해당 후보군이 문제의 조건을 만족하는지 여부를 확인해가며 해답을 찾는 알고리즘이다. 즉, 해를 찾는 도중에 해가 아니라면 이전 상태로 돌아가서 다시 해를 찾는 것이다. 이를 가지치기라고 한다. 이 가지치기를 얼마나 잘하느냐에 따라서 효율성이 결정된다고 한다. 하지만 최악의 문제에서는 지수함수의 시간복잡도가 걸리기 때문에 처리가 불가능한 경우도 있다고 한다. 완전탐색과 유사하지만 불필요한 탐색을 하지 않기 위해서 해가 아닌 경우를 탐색하지 않으므로 대규모 문제 풀이에 효과적이라는 장점이 있다. 하지만 구현하기가 어렵고 코드가 복잡해질 수 있다고 한다. 또한 최악의 경우에는 모든 경우의 수를 다 확인해야하는 경우도 있다.
백트래킹 알고리즘은 대부분 재귀함수로 구현된다. 재귀함수를 이용하면 코드가 간결해지고 코드의 가독성을 높일 수 있다.

• 코드의 형태

def 재귀함수(n):
	if 해가 맞으면:
    	출력 or 저장
    else: 해가 아니라면
    	for 모든 자식노드에 대해
        	if 정답이 가능성이 있다면(주어진 조건에 만족한다면):
            	자식 노드로 이동
                재귀함수(n+1)
                부모 노드로 이동

하지만 보통 정답의 가능성이 있는지 확인하는 부분을 별도의 함수로 만들어서 사용한다고 한다.

def 정답 가능성 체크(m)
	if 조건에 안 맞으면:
    	return False
    return True
    
def 재귀함수(n):
	if 해가 맞으면:
    	출력 or 저장
    else:
    	for 모든 자식노드에 대해
        	if 정답 가능성 체크(m):
            	자식 노드로 이동
                재귀함수(n+1)
                부모 노드로 이동

이러한 백트래킹은 스도쿠, N-Queen, 암호해독 등의 문제에서 활용된다고 한다.