[알고리즘] 백트래킹 (Back-tracking)

leeeha·2022년 7월 10일

알고리즘

목록 보기

12/20

출처: https://chanhuiseok.github.io/posts/algo-23/

🤷‍♀️ 백트래킹이 뭐야?

백트래킹의 이름에서 느껴지는 게 뭔가! 다시 돌아가서 추적한다? Yes!

백트래킹이란 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다고 한다.

DFS vs. 백트래킹

DFS (Depth-First Search)

깊이 우선 탐색 DFS는 가능한 모든 경로(후보)를 탐색한다. 불필요할 거 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 최적으로 줄이지 못한다. 따라서 N!의 경우의 수를 가지는 문제는 DFS로 처리하지 못할 가능성이 매우 크다.

백트래킹

백트래킹은 해를 찾아가는 도중에 지금의 경로가 해가 될 거 같지 않으면, 더 이상 깊이 들어가지 않고 이전 단계로 다시 돌아간다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 방향으로 나아가는 방식이기 때문에 DFS보다 효율적이다. 하지만, N!의 경우의 수를 가진 최악의 문제에서는 여전히 지수함수의 시간복잡도가 걸려서 처리가 불가능할 수도 있다. 따라서, 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다! 즉, 답이 될만한 가능성이 없으면 더 이상 탐색을 진행하지 않고 가지치기를 하면서 최적해를 구하는 것이다.

주로 문제풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문을 걸어서 답이 절대로 될 수 없는 상황을 정의하고, 그런 상황일 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 다른 경우를 탐색하도록 구현할 수 있다.

한 가지 예시로 n개 중에 순서를 고려하지 않고 r개를 선택하는 조합 코드를 보자. DFS로 깊이 있게 탐색하다가 r개를 모두 선택한 경우에는 현재 가지에 대한 탐색을 종료한다. 그리고 다음 경우의 수에 대한 탐색을 위해 상태를 복구하고 다시 재귀 호출을 반복한다. 따라서 조합도 백트래킹의 예시라고 볼 수 있다.

void dfs(int cnt, int idx) { // 현재까지의 결과, 탐색을 진행할 인덱스 
	// r개를 선택한 경우 
	if(cnt == r) { 
    	// 결과 처리 후 현재 가지에 대한 탐색 종료 
        return; 
    }
    
    // r개를 선택하지 않은 경우 재귀 호출 반복 
	for(int i = idx; i < n; i++){ 
    	if(!selected[i]){
			selected[i] = true; // 상태 변화 
			dfs(cnt + 1, i); // 재귀 호출
			selected[i] = false; // 다음 경우의 수를 위해 상태 복구 
		}
    }
}