[자료구조] Backtracking 기법

[자료구조] Backtracking 기법

 

DFS와는 다르게 탐색중인 경로에 답이 없다고 판단시 탐색시작 노드의 부모로 되돌아가 다른 방향으로 탐색하는 기법

해당 경로에 답이 있을 것 같은 경우 "유망하다"라고 말한다

DFS 탐색에서 유망한 조건만을 만족하는 방향만을 살펴보는 방식

 

def dfs():
	if promising(x):
    	dfs()
        
def promising(x):
	if 유망한경우 : return True
    return False

 

예제1. 백준 9663

백준 9663

백트래킹 이용

DFS를 수행하면서, 유망하지 않은 경로면 빽

출처

[Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기