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

 DFS 탐색 중 가능성이 없는 방향은 가지 않는 '백트래킹' 기법에 대해서 알아보겠습니다.

 

 

[ Contents ]

 

 

1. DFS

2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자

깊이 우선 탐색(DFS): 방문하지 않은 인접 노드가 없을 때까지 탐색하여 한 곳씩 마무리하는 방식

 DFS는 끝이 나올 때까지 한 방향으로 탐색하는 방식입니다. 끝장을 볼 때까지는 계속 한 곳만 탐색하기 때문에, 방향을 잘못 선정하면 손해가 큽니다.

 따라서, 잘못된 방향이면 바로 잡아줄 고삐가 필요합니다.

 

 

 

2. 백트래킹(Backtracking)

가지치기(Pruning)

백트래킹(Back Tracking): 해당 방향에 답이 없다고 판단되면, 되돌아가서 다른 방향을 탐색하는 기법

 탐색 중인 경로에 답이 없다고 판단되면, 탐색을 시작했던 노드의 부모에서 다른 방향으로 탐색합니다. 불필요한 부분을 끝까지 탐색하지 않기에, 가지치기(Pruning)라고도 합니다. 가지치기를 잘하면, 탐색 시간을 현저히 줄일 수 있습니다.

 반면, 해당 경로에 답이 있을 것 같으면 유망하다(Promising)라고 합니다. 단순히 답이 없다는 근거가 없는 상태로, 포퍼의 반증주의와 유사합니다.

 즉, 백트래킹은 DFS 탐색에서 유망한 조건을 만족하는 방향만 살펴보는 방식입니다.

 

 

 

3. 구현 코드

def dfs():
	# 유망하면 계속해서 dfs탐색
	if promising(x):
		dfs()

def promising(x):
	if 유먕 여부: return True
    	return False

 유망 여부를 판단해서 DFS( ) 탐색을 계속 이어갈지 결정합니다. 백트래킹은 기존의 DFS 탐색에서 유망 여부를 미리 판단해서 최적화시킨 알고리즘입니다.

 

2022.03.21 - [Algorithm] - [탐색/백트래킹] 백준 9663 N-Queen - 파이썬(Python)

[탐색/백트래킹] 백준 9663 N-Queen - 파이썬(Python)

 예제는 위 링크에 있습니다. 혹은 티스토리 검색에 '백트래킹'을 치셔면 다른 예제들을 보실 수 있습니다.