[알고리즘] 백트래킹(backtracking) 문제 정복 커리큘럼

서론

백트래킹(Backtracking)은 주로 BFS 및 DFS와 같은 모든 경우의 수를 탐색하는 완전 탐색 대신 중간에 더 이상 조건을 충족하지 못하는 경우 이하 탐색을 종료하고 조건을 충족하는 다른 경우를 탐색하는 기법입니다. 완전 탐색에 비해 성능이 좋은 장점이 있습니다. 

 

솔루션 예

백트래킹 문제는 다음과 같은 형식으로 솔루션을 작성하면 쉽게 풀 수 있습니다.

• 조건을 만족하지 않는 경우를 모두 체크하는 것이 아닌 조건을 모두 만족하는 경우만 체크
• 조건을 만족하는 경우들을 이하 반복문을 통해 재귀 탐색

def backtracking(tmp_answer):
	# 조건을 모두 만족하는 경우를 조건문으로 처리합니다.
	if answer == tmp_answer:
    	return True
     
    for i in (추가 탐색해야 하는 조건 경우들):
    	backtracking(tmp_answer)

backtracking(첫 번째 답)

대부분의 문제를 위와 같은 방식으로 솔루션을 작성하면 됩니다. 

 

문제 커리큘럼

기본 문제

간단한 백트래킹 기법을 사용하면 풀 수 있는 문제입니다.

Generate Parentheses - LeetCode

 

매트릭스 활용

조금 난이도를 올려보겠습니다. 매트릭스 자료 구조를 활용해서 풀여야 합니다.

Word Search - LeetCode

매트릭스는 아래와 같은 방식으로 상 하 좌 우를 모두 감안해야 합니다. 모두 재귀로 실행하되 함수 실행 시 제일 처음 올바르지 않는 것이 포인트입니다.

def backtracking(ROW, COL):
	if ROW < 0 or ROW > ROW_LENGTH-1 or \
    	COL < 0 or COL > COL_LENGTH-1 or \
        기타 조건:
        return False
       
     backtracking(ROW-1, COL)
     backtracking(ROW, COL-1)
     backtracking(ROW+1, COL)
     backtracking(ROW, COL+1)

위 방법 대신 다른 스타일로도 솔루션을 작성할 수 있지만 위 방법을 추천드립니다.

 

N-Queens

아주 유명한 문제입니다. 조금 난이도가 있습니다.

N-Queens - LeetCode