[Algorithm] 백트래킹(Backtracking)

백트래킹(backtracking)이란?

모든 경우의 수를 전부 고려하는 알고리즘으로 해를 찾는 도중 조건에 맞지 않으면 되돌아가서 다시 해를 찾아가는 기법

특징

• 상태 공간 트리를 탐색하는 일종의 트리 탐색 알고리즘이다.
• 코딩에서는 불필요한 경로를 조기에 차단하여 반복문의 횟수를 줄일 수 있으므로 효율적인 방법이다.
• 하지만 N! 경우의 수는 최악의 경우 여전히 지수함수 시간을 필요로 가방법이 효율성이 결정한다.

동작 과정

1. 방문 중인 노드가 유망한지 체크한다.

• 유망함(promising): 방문 중인 노드에서 하위 노드가 해답을 발견할 가능성이 있는 것
• 유망하지 않음(nonpromising):  하뒤 노드에서 해답을 발견할 가능성이 없는 것

2. 유망하지 않으면, 부모노드로 돌아간다.(백트래킹)

3. 이때 하위 노드는 방문하지 않는다. = 가지치기(Purning) 

def 재귀함수(x):
	if 정답이라면:
    	정답 출력 혹은 결과 저장
    else:
    	for 현재 노드의 모든 자식 노드에 대해:
        	if 현재 상태가 유망하다면:
            	자식노드로 이동
                재귀함수(x+1)
                부모노드로 이동(백트래킹)

백트래킹과 DFS

• 방식에 따라서 DFS, BFS, 최선 우선 탐색(Best First Search/HeuristicSearch)로 구현할 수 있다.
• 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다.
• 모든 경우의 수를 고려해야 하는 문제라면, 일반적으로 DFS가 편리하다.
• 모든 경우의 수를 탐색하는 과정에서, 조건문으로 답이 될 수 없는 상황을 정의하고, 조건에 맞지 않으면 탐색을 중단하고 이전으로 돌아가서 다시 다른 경우를 탐색하는 것을 반복하여 조건에 맞는 정답을 찾는다.

대표적인 문제 모음

Backtracking 문제 리스트